Ruby (RMXP) > Verschiedene, einzigartige, Kombinationen mehrerer Arrays ermitteln

[Linkey]

Hallo zusammen,

ich habe da momentan ein kleines Problem. Und zwar habe ich ein Array, welches aus Arrays besteht. In den einzelnen Arrays sind ganze Zahlen hinterlegt. Nun möchte ich anhand dessen mögliche Kombinationen ermitteln, wobei eine Kombination nur unterschiedliche Werte beinhalten darf. Sowohl die Anzahl der Arrays, als auch die Anzahl der Elemente pro Array sind dynamisch.

Beispiel:
Array = [[0,1,2],[0,1,2],[1,2]]

In diesem Beispiel würde es 4 verschiedene Kombinationen geben:
[0,1,2]
[0,2,1]
[1,0,2]
[2,0,1]

Ich selbst brauche nur eine einzige Kombination, weshalb ich das ganze über Rekurssion gelöst habe. Für jedes Element des ersten Arrays rufe ich eine Methode auf, welcher ich das aktuelle "kombinationsarray" und den index des nächsten Arrays übertrage.
Diese Methode ruft sich selbst dann solange auf, bis das Kombinationsarray komplett ist.

Also auf das oben bezogene Beispiel:


testArray = [[0,1,2],[0,1,2],[1,2]]

p(testArray.get_combi())

def get_combi(arr=[],index=0)
self[index].each do |ta|
unless(arr.include?(ta))
if((index+1)<self.size())
tcombi = get_combi(arr<<ta,index+1)
return tcombi if(tcombi.size == self.size)
else
return (arr<<ta)
end
end
return nil
end


Ausgabe: [0,1,2]


Nun zu meiner Frage, gibt es da noch andere (eventuell performantere) Wege, dies umzusetzen? Und wenn man nun doch alle Kombinationen ermitteln möchte, was wäre die performanteste Lösung dafür? (Sprich, dass im oben genannten Beispiel die vier Kombinationen zurückgegeben werden)

[Cornix]

Vielleicht wäre es besser für dich falls du uns verraten würdest für welche Art von Anwendung du diese Funktion brauchst. Denn vielleicht gibt es ganz allgemein eine einfachere Lösung zu dem Gesamtproblem.
Wenn du tatsächlich alle Kombinationen herausfinden willst so wird dein Algorithmus zwangsweise eine schlechte Laufzeit haben müssen da soetwas immer ein aufwendiger Prozess ist.
Ruby selbst ist ebenfalls nicht sonderlich schnell, besonders die Implementierung des RMXP.

[Fatalis]

Ich würde mir um die Laufzeit nicht besonders viele Gedanken machen. Ich nehme mal an, dass die Anzahl der Arrays und die Anzahl der Elemente höchstens im zweistelligen Bereich liegt, da ist es eigentlich noch recht irrelevant, ob man quadratische oder lineare Laufzeit hat.
Man könnte sich natürlich viele Gedanken machen und das Ganze sehr viel effizienter lösen, Frage ist halt ob es den Aufwand dafür rechtfertigt.

Für Ideen kann man immer die Array-Dokumentation (http://www.ruby-doc.org/core-1.9.3/Array.html) durchforsten, ob eine Methode etwas in die richtige Richtung macht.
product sieht mir spontan schon recht ähnlich aus zu dem, was du machen willst.
Ich hab jetzt nicht überprüft, ob es die Methoden auch in der Ruby-Version vom RmXP gibt, aber so könnte man es mit recht wenig Code machen.

Product liefert alle mögliche Kombinationen ohne Überprüfung, ob ein Element mehrfach vorkommt.
Da product auf einem array aufgerufen wird (in diesem Fall auf einem Teilarray des Gesamtarrays) und als Parameter die weiteren Arrays bekommt, sieht der Aufruf vielleicht etwas komisch aus. a.product() ohne Parameter würde nicht das richtige machen.
Außerdem gehört das * noch vor den Parameter, da man die Arrays als Parameterliste und nicht als zusammengehörigeres Array benötigt. Ich hoffe das wird hier nicht zu kompliziert zu verstehen...
uniq entfernt alle doppelten Elemente aus dem Array, wenn es keine gibt, bleibt das Array gleich und die Kombination ist gültig.
Das Ganze verketten und man hat eine Lösung mit zumindest recht übersichtlichem Code.


def get_all_combinations(a)
a.first.product(*a[1..a.length-1]).select{|b| b.uniq==b}
end

Ansonsten könnte man auch einfach über alle Arrays iterieren und so die Kombinationen finden.

Edit:
Code korrigiert, da man product eine Parameterliste von Arrays und nicht ein Array von Arrays übergeben muss

[Linkey]

Vielen Dank für eure Antworten.
Ja wie schon beschrieben, ich selbst benötigte ja nur eine Kombination. Wollte halt aus Interesse wissen, was es da noch so für Methoden gibt.

Ja in meinem Beispiel habe ich maximal 8 Arrays mit je 8 Werten. Performance sollte da nicht wirklich auffallen.

Ich hab mal die product Methode hinzugefügt. In der RMXP Ruby Version war die noch nicht vorhanden, glaube ich.
Funktioniert super damit.

[-KD-]

Die ganzen Enumerator-Methoden wie product, combination etc. sind erst ab Ruby 1.9 (und damit RPGMaker VXAce) verfügbar. Aber dein rekursiver Code ist noch fehlerhaft: Du suchst in jedem Schritt nach einem Element, dass noch nicht ausgewählt wurde. Dabei berücksichtigst du keine "Sackgassen", also dass du früh eine Entscheidung triffst die alle möglichen Lösungen verbaut.

Beispiel: Rufe mal deine Methode mit dem Array [[0, 1, 2], [0, 1, 2], [0]] auf. Deine Methode wird erst die 0 wählen, dann die 1 und danach feststellen, dass es keine Lösung gibt die mit 0 und 1 anfängt und abstürzen. Wenn du schon rekursiv programmierst, musst du eine ordentliche Abbruchsbedingung einbauen, damit der Algorithmus zurückgeht und eine andere Kombination ausprobiert. Das würde dann so aussehen:

class Array
def get_combi(arr=[],index=0)
return arr if index >= size
self[index].each do |ta|
unless arr.include? ta
arr << ta
rekursion = get_combi arr, index+1
# Wenn nil zurückgegeben wird, ist keine Lösung mit arr möglich!
return rekursion if rekursion
# mache Änderung an arr wieder rückgängig für nächsten Versuch
arr.pop
end
end
return nil # abbruch
end
end

Alternativ hier noch eine iterative Variante:

class Array
def uniq_combi
indizes = Array.new(size, 0)
set = {}
k = 0
while k < size
while set[self[k][indizes[k]]]
indizes[k] += 1
while indizes[k] >= self[k].size
indizes[k] = 0
k -= 1
return nil if k < 0
set[self[k][indizes[k]]] = false
indizes[k] += 1
end
end
set[self[k][indizes[k]]] = true
k += 1
end
i= -1
return indizes.map {|index| self[i+=1][index]}
end
end

[Linkey]

Hey KD,

danke für deine Antwort. Ich hatte so eine Abfrage schon in der Methode, ich hatte die Methode von der Arbeit aus aus dem Kopf, in der schnelle, getippt x)