Rekursiver Algorithmus zum finden von Kombinationen von einem Satz in Java

Ich versuche zu finden, einige Beispiele zu finden, die eine gegebene Menge s (kann eine Zeichenfolge oder ein array von ganzen zahlen) alle Kombinationen in Java. Und ich stieß auf dieses code-Stück (gefunden in http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html. Ich habe kopiert nur die entsprechenden Teile hier.):

//print all subsets of the characters in s
public static void comb1(String s) { comb1("", s); }

//print all subsets of the remaining elements, with given prefix 
private static void comb1(String prefix, String s) {
    if (s.length() > 0) {
        System.out.println(prefix + s.charAt(0));
        comb1(prefix + s.charAt(0), s.substring(1));
        comb1(prefix,               s.substring(1));
    }
}  

//read in N from command line, and print all subsets among N elements
public static void main(String[] args) {
   int N = Integer.parseInt(args[0]);
   String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
   String elements = alphabet.substring(0, N);

   //using first implementation
   comb1(elements);
   System.out.println();
}

Aber ich verstehe wirklich nicht, wie es funktioniert. Hat jemand darauf zu erklären?

Ist es der code, den Sie Probleme mit, oder ist es das grundlegende Prinzip? Möchten Sie vielleicht einen Stift und Papier und gehen Sie über eine kleine Probe. Beginnen Sie mit N=2 und Folgen Sie, was der code tut mit "abc".

InformationsquelleAutor Ahmet Ikras | 2011-08-06

  1. 0

    Java-Programme starten am main. Dieses eine argument sollte ein integer sein. Es speichert die ganze Zahl N. Wenn der Benutzer eingegeben in java und das Programm name mit 3, dann wäre N auf 3 festgelegt. Diese wird verwendet, um ziehen Sie die ersten N Buchstaben des Alphabets, und legen Sie Sie in Elemente. (In unserem Beispiel abc). Dann ruft er comb1(abc), das heißt, die öffentliche comb1 zuerst aufgeführt.

    Nächsten comb1 ruft die private comb1 mit zwei Argumenten, eine leere Zeichenfolge und abc.

    Nun die Rekursion beginnt. Private comb1 nimmt einen Präfix und einen string (im ersten Fall ein leerer string und abc). Wenn der string nicht leer ist, dann ist es:

    1. druckt der erste char
    2. ruft sich selbst rekursiv mit der Vorwahl + die ersten Zeichen als der neue Präfix und den Rest wie die neue Zeichenfolge und
    3. ruft sich selbst rekursiv mit dem gleichen Präfix, das neue Präfix und alle, aber das erste Zeichen als der neue string.

    (Hier ist, wo viele Menschen zittern leicht... es anstarren, hängen, werden die computer, und die Bedeutung wird kommen.)

    (Top level)
comb1("", "abc") -> *1* a   *2* comb1("a", "bc") *3* comb1("", "bc")

(Second level)
comb1("a", "bc") -> *1* ab  *2* comb1("ab", "c") *3* comb1("a", "c")
comb1("", "bc")  -> *1* b   *2* comb1("b", "c")  *3* comb1("", "c")

(Third level)
comb1("ab", "c") -> *1* abc *2* comb1("abc", "") *3* comb1("ab", "")
comb1("a", "c")  -> *1* ac  *2* comb1("a", "")   *3* comb1("a", "")

comb1("b", "c")  -> *1* bc  *2* comb1("bc", "")  *3* comb1("b", "")
comb1("", "c")   -> *1* c   *2* comb1("c", "")   *3* comb1("", "")

(Fourth level)
comb1("ab", "") -> (immediate return, ending recursion) 
comb1("a", "") -> (immediate return, ending recursion)
comb1("b", "") -> (immediate return, ending recursion)
comb1("", "") -> (immediate return, ending recursion)

    InformationsquelleAutor rajah9

  2. 3

    Erstellen alle Kombinationen eines bestimmten Satzes ist wirklich einfach. Du hast N Elemente, in jeder der Kombinationen eine element ist entweder vorhanden oder nicht, also hast du 2^N Kombinationen. Diese rekursive Funktion macht genau das. Es wählt jedes element aus dieser Liste aus, und schafft verbindungen, die enthalten es und schafft combintations welche nicht. Hinweis: es funktioniert nicht, drucken Sie die leere Kombination.

    Wenn es immer noch nicht klar, erstellen Sie eine kurze test-string (z.B.: 3 Zeichen), Feuer den debugger und sehen, wie es funktioniert.

    InformationsquelleAutor Karoly Horvath

Schreibe einen Kommentar