Berechnen Sie alle möglichen Kombinationen der angegebenen Zeichen

71635
Jamal

In meinem Lehrbuch Lectures on Discrete Mathematics für Informatik wurde ich gebeten, ein Programm zu konstruieren, das ein Alphabet ( {a,b,c}oder eine beliebige Zeichenkombination {1,4,s,a}) sowie einen Längenwert und alle möglichen Kombinationen dieses Alphabets berechnet.

Zum Beispiel:

char[] alphabet = new char[] {'a','b'};
possibleStrings(3, alphabet,"");

Dies wird ausgegeben:

aaa
aab
aba
abb
baa
bab
bba
bbb

Das sind alle Kombinationen des Alphabets {a, b, c} mit der Zeichenfolgenlänge 3.

Der Code, den ich geschrieben habe, ist funktional, jedoch würde ich gerne lesen, was ich falsch mache oder vielleicht besser mache. Das Buch gab kein Beispielprogramm, deshalb hoffe ich nur, dass es genau das ist, wonach es gesucht hat, aber vielleicht gibt es einen viel besseren Weg, es zu verbessern, oder wie ich es verbessern kann. Vielleicht ist das in Ordnung, aber ich brauche nur jemanden, der es sich anschaut und es mir sagt.

public class Program {

    public static void main(String[] args) {

        // Create an alphabet to work with
        char[] alphabet = new char[] {'a','b'};
        // Find all possible combinations of this alphabet in the string size of 3
        StringExcersise.possibleStrings(3, alphabet,"");
    }

} class StringExcersise {

    public static void possibleStrings(int maxLength, char[] alphabet, String curr) {

        // If the current string has reached it's maximum length
        if(curr.length() == maxLength) {
            System.out.println(curr);

        // Else add each letter from the alphabet to new strings and process these new strings again
        } else {
            for(int i = 0; i < alphabet.length; i++) {
                String oldCurr = curr;
                curr += alphabet[i];
                possibleStrings(maxLength,alphabet,curr);
                curr = oldCurr;
            }
        }
    }
}
Antworten
5

3 Antworten auf die Frage

3
radai

Ihr Code sieht gut aus.

  • Eine geringfügige Leistungsverbesserung, die ich durchführen würde, ist das Übergeben eines StringBuilder anstelle eines String. Ein String in Java ist unveränderlich. curr += alphabet[i]Daher müssen Sie bei jedem Aufruf tatsächlich ein neues String-Objekt zuordnen. Stattdessen können Sie das Zeichen an einen StringBuilder anhängen (und beim Verlassen das letzte Zeichen löschen), um die Anzahl der während des Laufs erstellten Objekte zu speichern
  • for(int i = 0; i < alphabet.length; i++) {}könnte als modernere Schleife neu geschrieben werden for (char c : alphabet) {}, was zu einem besser lesbaren Ergebnis führt
Ich glaube, die Compiler-Optimierung würde String in StringBuilder konvertieren. vor 6 Jahren 0
@Vinay - wenn es eine gerade lange Liste von "+" - Ops war, hast du recht. Ich bin in diesem Fall nicht so sicher. radai vor 6 Jahren 1
@Vinay Ich bezweifle es auch in diesem Fall. Vojta vor 6 Jahren 0
Hängt von der Implementierung des Compilers ab, einige konvertieren nicht für Java Olu Smith vor 3 Jahren 0
2
DerekRFagan

If the sequence is quite large then recursive methods can use up too much memory. This iterative approach works quite well.

private void generateCombinations(int arraySize, ArrayList<String> possibleValues)
{
    int carry;
    int[] indices = new int[arraySize];
    do
    {
        for(int index : indices)
            System.out.print(possibleValues.get(index) + " ");
        System.out.println("");

        carry = 1;
        for(int i = indices.length - 1; i >= 0; i--)
        {
            if(carry == 0)
                break;

            indices[i] += carry;
            carry = 0;

            if(indices[i] == possibleValues.size())
            {
                carry = 1;
                indices[i] = 0;
            }
        }
    }
    while(carry != 1); // Call this method iteratively until a carry is left over
}
-1
user949300

Anstelle der oldCurr-Dateien erstellen Sie einfach jedes Mal eine newCurr-Datei. z.B

String newCurr = curr + alphabet[i];
possibleStrings(maxLength, alphabet, newCurr);

Wäre kürzer und zumindest für meine Augen viel klarer.

Danke, das war auch sehr hilfreich. Ich habe noch nie darüber nachgedacht. Prost. vor 6 Jahren 0
Dies führt dazu, dass bei jedem Start ZWEI neue Zeichenfolgen erstellt werden: `newCurr` und` curr + alphabet [i] ` TheCoffeeCup vor 6 Jahren 0
@Manny Meng Zuerst wird nur ein neuer String, newCurr, erstellt. Zweitens, da Strings unveränderlich sind, können Sie dies nicht vermeiden. Im OP-Code `curr + = alphabet [i] erstellt _ auch einen neuen String_. Dein Kommentar und Downvote sind also falsch. Selbst wenn ein zusätzliches Objekt erstellt wurde, kümmert sich in diesem Beispiel niemand darum, es sind nur 10 zusätzliche Objekte. user949300 vor 5 Jahren 0
Guter erster Punkt, aber für den zweiten Punkt kann `curr + = alphabet [i]` leicht mit einem `StringBuilder` gelöst werden, wie die akzeptierte Antwort nahelegt. Außerdem sind 10 zusätzliche Objekte viel, wenn Sie dies Tausende oder Millionen Mal ausführen. Wenn zum Beispiel die am meisten optimierte Methode (dh keine zusätzlichen Objekte) innerhalb von 10 Millisekunden ausgeführt wird und die andere Methode 11 Millisekunden dauert, ist dies ein Unterschied von 1.000 bis 1.000.000 Millisekunden. TheCoffeeCup vor 5 Jahren 0
Auf den StringBuilder wird schließlich über `toString ()` zugegriffen, um ein Objekt zu erstellen. Nirgends schlägt OP vor, dass dies Tausende Male genannt wird, geschweige denn Tausende von Millionen. user949300 vor 5 Jahren 0
Es kann mehrmals aufgerufen werden, und manchmal ist der kleine Zeitunterschied von entscheidender Bedeutung. Und ein Objekt ist besser als 10. TheCoffeeCup vor 5 Jahren 0