Algorithmus, um alle Kombinationen der Größe n aus einem Array (Java) zu erhalten? [closed]

Im Moment versuche ich, eine Funktion zu schreiben, die ein Array und eine ganze Zahl n verwendet und eine Liste jeder Kombination der Größe n (also eine Liste von int-Arrays) liefert. Ich kann es mit n verschachtelten Schleifen schreiben, aber dies funktioniert nur für eine bestimmte Größe einer Teilmenge. Ich kann nicht herausfinden, wie ich es verallgemeinern kann, um für jede Kombinationsgröße zu funktionieren. Ich denke, ich muss Rekursion verwenden?

Dies ist der Code für alle Kombinationen von 3 Elementen, und ich brauche einen Algorithmus für eine beliebige Anzahl von Elementen.

import java.util.List;
import java.util.ArrayList;

public class combinatorics{
    public static void main(String[] args) {

        List<int[]> list = new ArrayList<int[]>();
        int[] arr = {1,2,3,4,5};
        combinations3(arr,list);
        listToString(list);
    }

    static void combinations3(int[] arr, List<int[]> list){
        for(int i = 0; i<arr.length-2; i++)
            for(int j = i+1; j<arr.length-1; j++)
                for(int k = j+1; k<arr.length; k++)
                    list.add(new int[]{arr[i],arr[j],arr[k]});
    }

    private static void listToString(List<int[]> list){
        for(int i = 0; i<list.size(); i++){ //iterate through list
            for(int j : list.get(i)){ //iterate through array
                System.out.printf("%d ",j);
            }
        System.out.print("n");
        }
    }
}

Dies ist ein gut untersuchtes Problem der Erzeugung aller k-Teilmengen, oder k-Kombinationen, die ohne Rekursion leicht durchgeführt werden kann.

Die Idee ist, eine Reihe von Größen zu haben k Halten der Reihenfolge von Indizes von Elementen aus dem Eingabearray (das sind Zahlen aus 0 zu n - 1) in aufsteigender Reihenfolge. (Teilmenge können dann erstellt werden, indem Elemente nach diesen Indizes aus dem anfänglichen Array genommen werden.) Wir müssen also alle diese Indexsequenzen generieren.

Die erste Indexsequenz ist [0, 1, 2, ... , k - 1], im zweiten Schritt wechselt es zu [0, 1, 2,..., k], dann zu [0, 1, 2, ... k + 1] und so weiter. Die letztmögliche Reihenfolge ist [n - k, n - k + 1, ..., n - 1].

Bei jedem Schritt sucht der Algorithmus nach dem Element, das dem Endelement am nächsten ist, das inkrementiert werden kann, erhöht es und füllt Elemente bis zu diesem Element auf.

Betrachten Sie zur Veranschaulichung n = 7 und k = 3. Erste Indexfolge ist [0, 1, 2], dann [0, 1, 3] und so weiter… Irgendwann haben wir [0, 5, 6]:

[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements

next iteration:

[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"

Daher, [0, 5, 6] wird gefolgt von [1, 2, 3], dann gehts [1, 2, 4] etc.

Code:

int[] input = {10, 20, 30, 40, 50};    // input array
int k = 3;                             // sequence length   

List<int[]> subsets = new ArrayList<>();

int[] s = new int[k];                  // here we'll keep indices 
                                       // pointing to elements in input array

if (k <= input.length) {
    // first index sequence: 0, 1, 2, ...
    for (int i = 0; (s[i] = i) < k - 1; i++);  
    subsets.add(getSubset(input, s));
    for(;;) {
        int i;
        // find position of item that can be incremented
        for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--); 
        if (i < 0) {
            break;
        }
        s[i]++;                    // increment this item
        for (++i; i < k; i++) {    // fill up remaining items
            s[i] = s[i - 1] + 1; 
        }
        subsets.add(getSubset(input, s));
    }
}

// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
    int[] result = new int[subset.length]; 
    for (int i = 0; i < subset.length; i++) 
        result[i] = input[subset[i]];
    return result;
}

Wenn ich dein Problem richtig verstanden habe, Dies Artikel scheint darauf hinzuweisen, was Sie zu tun versuchen.

Um aus dem Artikel zu zitieren:

Methode 1 (Elemente fixieren und wiederholen)

Wir erstellen ein temporäres Array ‘data[]’, das alle Ausgaben nacheinander speichert. Die Idee ist, mit dem ersten Index (Index = 0) in den Daten zu beginnen[], Elemente an diesem Index nacheinander fixieren und für verbleibende Indizes wiederholen. Das Eingabearray sei {1, 2, 3, 4, 5} und r sei 3. Zuerst fixieren wir 1 am Index 0 in data[], dann wiederkehren für die verbleibenden Indizes, dann fixieren wir 2 bei Index 0 und wiederholen sich. Schließlich beheben wir 3 und wiederholen uns für die verbleibenden Indizes. Wenn die Anzahl der Elemente in den Daten[] gleich r (Größe einer Kombination), wir drucken Daten[].

Methode 2 (Einschließen und Ausschließen jedes Elements)

Wie bei der obigen Methode erstellen wir ein temporäres Array data[]. Die Idee hier ähnelt dem Teilmengensummenproblem. Wir betrachten nacheinander jedes Element des Eingabearrays und wiederholen uns in zwei Fällen:

1. Das Element ist in der aktuellen Kombination enthalten (Wir setzen das Element in Daten[] und inkrementiere den nächsten verfügbaren Index in den Daten[])
2. Das Element ist in der aktuellen Kombination ausgeschlossen (Wir setzen das Element nicht und ändern den Index nicht)

Wenn die Anzahl der Elemente in den Daten[] gleich r (Größe einer Kombination) werden, drucken wir es.

Sie können dies definitiv mit Iteration tun.

Hier ist eine Lösung, die berechnet, wie viele Arrays wir erstellen sollten, und sie dann mithilfe von Mathematik erstellt, um zu berechnen, welches Element aus dem Quellarray an welcher Stelle sein sollte:

public static void combinations(int n, int[] arr, List<int[]> list) {
    // Calculate the number of arrays we should create
    int numArrays = (int)Math.pow(arr.length, n);
    // Create each array
    for(int i = 0; i < numArrays; i++) {
        int[] current = new int[n];
        // Calculate the correct item for each position in the array
        for(int j = 0; j < n; j++) {
            // This is the period with which this position changes, i.e.
            // a period of 5 means the value changes every 5th array
            int period = (int) Math.pow(arr.length, n - j - 1);
            // Get the correct item and set it
            int index = i / period % arr.length;
            current[j] = arr[index];
        }
        list.add(current);
    }
}

Aktualisieren:

Hier ist eine optimierte Version, die die Anzahl der Anrufe deutlich reduziert auf Math.pow

public static void combinations(int n, int[] arr, List<int[]> list) {
    // Calculate the number of arrays we should create
    int numArrays = (int)Math.pow(arr.length, n);
    // Create each array
    for(int i = 0; i < numArrays; i++) {
        list.add(new int[n]);
    }
    // Fill up the arrays
    for(int j = 0; j < n; j++) {
        // This is the period with which this position changes, i.e.
        // a period of 5 means the value changes every 5th array
        int period = (int) Math.pow(arr.length, n - j - 1);
        for(int i = 0; i < numArrays; i++) {
            int[] current = list.get(i);
            // Get the correct item and set it
            int index = i / period % arr.length;
            current[j] = arr[index];
        }
    }
}