Ich suche nach einem Algorithmus, um die einfachste Kombination von ganzen Zahlen von 0 bis 5 (das ist die, die aus der kleinsten Anzahl von ganzen Zahlen besteht) zu finden, die noch nicht benutzt wurde (die verwendeten Kombinationen sind in einer Liste).
Die Reihenfolge ist wichtig und die Kombinationen sollten in einer Liste zurückgegeben werden.
Zum Beispiel könnte die Liste mit den verwendeten Nummern wie folgt aussehen:
{{0}, {1}, {2}, {3}, {4}, {0,0}, {0,1}, {0,2}, ..., {2,1 }, {2,2}, ..., {1,5,4}, ...}
In diesem Fall sollte der Algorithmus eine Liste mit {5} zurückgeben, da {5} die Kombination ist, die aus den wenigsten ganzen Zahlen besteht.
Wenn die Liste so aussieht:
{{0}, {1}, {2}, {3}, {4}, {5}, {0,0}, {0,1}, {0,2}, {0,3 }, {0,5}, ...}
Der Algorithmus sollte eine Liste mit 0 und 4 ({0,4}) zurückgeben.
Wie es in Java zu verwenden ist, ist eine Java-Antwort vorzuziehen, aber Pseudo-Code oder andere Programmiersprachen sind ebenfalls verwendbar.
Vielen Dank im Voraus!
Ich denke, Beispiel 2 ist falsch: für {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2}, {0,3}, {0,5}, ...} kleinste Lösung ist {0,0}, nicht {0,4}
Vollständige Lösungen finden Sie hier:
%Vor%Wenn die Liste, die Sie haben, geordnet ist, gibt es zwei Methoden, die mir besser erscheinen als eine lineare Suche.
Unter der Annahme, dass Sie den Kombinationsraum nicht vollständig ausfüllen, können Sie eine Variante einer binären Suche verwenden.
Zuerst lasst uns jede Gruppe der Größe 'x' eine Gruppe aufrufen. Also, 0,1,2,3,4,5 ist die Gruppe 1, {0,0} bis {5,5} ist die Gruppe 2.
Beginnend mit Gruppe 1, überprüfen Sie die Listenposition, die den letzten Wert in der Gruppe enthält, wenn sie alle dort waren. ZB List[5] == 5 . Wenn dies der Fall ist, fahren Sie mit Gruppe 2 fort und wiederholen Sie die Übung. Wenn dies nicht der Fall ist, führen Sie eine binäre Suche nur in der Gruppe durch, die immer die untere Seite favorisiert, schließlich finden Sie den ersten fehlenden Wert.
Andernfalls, wenn Sie erwarten, den gesamten Kombinationsraum zu verwenden, führen Sie eine binäre Suche für den gesamten Kombinationsraum durch und prüfen Sie, ob der Wert an der Position dem erwarteten Wert entspricht, wenn alle vorhergehenden Werte vorhanden waren.
Probieren Sie einfach jede Kombination aus, beginnend mit der kürzesten, und stoppen Sie, wenn Sie eine haben, die nicht verwendet wird? Hast du das versucht, es scheint wirklich sehr offensichtlich?
Für dieses Problem würde ich ein spezifisches Objekt erstellen, um ein Element zu speichern (einzelne Zahl oder Tupel der Zahl):
%Vor%Der Schlüssel wäre die Verkettung der Zahlen, geordnet. In Ihrem Beispiel wären die Tasten "0" "1" "2" 3 "4" 5 "01" 02 "03" "05".
Sie können eine Map verwenden, um die Tupel mit dem Assoziationsschlüssel - Wert zu speichern.
Da die Schlüssel eine logische Reihenfolge einhalten, ist es einfach, das nächste freie Tupel zu finden. Sie beginnen einfach mit "0" und inkrementieren den Schlüssel (indem Sie die definierte Reihenfolge verwenden) und checken die Karte ein, um zu überprüfen, ob das Tupel bereits verwendet wird oder nicht.
In diesem Beispiel hat das erste freie Tupel die Taste "04". Von diesem Schlüssel aus ist das Erstellen des zugehörigen Tuple einfach.
Tags und Links algorithm java combinatorics combinations