Graph Permutationen

[Pfaeff]

Hallo,
Ich habe verschiedene Listen. Diese haben eine bestimmte Reihenfolge (Liste1, Liste2, ...)
Jetzt möchte ich eine Liste von Listen erstellen, welche sämtliche Kombinationen unter Beachtung der Reihenfolge liefert. (1. element der ersten liste + erstes element der zweiten liste usw.)
Hier mal eine kleine Grafik zur Anschauung:

Mein Ansatz sah dazu bisher so aus:

        int current=0, line=1, row=0;
        ArrayList test= new ArrayList();
        while (current < v[0].size()) {
           // test.add(v[line].get(row));
            row++;
            if (row >= v[line].size()) {
                line++;
                row = 0;
                if (line >= v.length) {
                    current++;
                    line = 1;
                }
            }
        }

Dieser liefert mir Permutationen aber nicht so wie ich es gerne hätte. Es scheinen auch viel zu wenige zu sein.

Hoffe mir kann geholfen werden,

Vielen Dank

 

[Ebenius]

Eine nicht optimierte Lösung sieht so aus und funktioniert: [HIGHLIGHT="Java"]public static void main(String[] args) {
final Collection[] input =
{ Arrays.asList(new String[] { "A", "B", "C" }), //
Arrays.asList(new String[] { "D", "E", "F", "G" }), //
Arrays.asList(new String[] { "H", "I" }), //
Arrays.asList(new String[] { "J", "K", "L", "M" }) //
};
final List collector = new LinkedList();
collectPermutations(input, 0, new LinkedList(), collector);
for (Iterator it = collector.iterator(); it.hasNext() {
final List element = (List) it.next();
System.out.println(element);
}
}

static void collectPermutations(
Collection[] input,
int level,
List tail,
List collector) {
final Collection in = input[level];
for (Iterator it = in.iterator(); it.hasNext() {
final List newTail = new ArrayList(input.length);
newTail.addAll(tail);
newTail.add(it.next());
if (input.length == level + 1) {
// this is the last element
collector.add(newTail);
} else {
collectPermutations(input, level + 1, newTail, collector);
}
}
}[/HIGHLIGHT]
Ich habe den Code mal für Java 1.4 kompatibel gelassen (keine Generics), da Dein Code das auch ist.

Ebenius

 

[Pfaeff]

Prinzipiell handelt es sich ja um eine mehrfach dynamisch verschachtelte for-Schleife. Dazu muss es doch ein (nicht allzu kompliziertes) äquivalent als while-Schleife geben oder? Ich hab ein wenig probiert, mir arrays für die indizes gebaut, aber irgendwie hats net ganz hingehauen. An Rekursion dachte ich auch schon, aber eigentlich wollte ich das vermeiden.

mfg

 

[0x7F800000]

Warum nicht rekursiv? Da solche Kombinatorische Sachen eh enorm viel Speicher fressen, ist der callstack verbrauch eher vernachlässigbar, dafür ist das schön simpel zu formulieren:
[HIGHLIGHT="Java"]
public static <T> Collection<List<T>> getAllCombinations(List<List<T>> lists){
Collection<List<T>> result=new LinkedList<List<T>>();
if(lists.size()==0){
result.add(new LinkedList<T>());
}else{
List<T> tailList=lists.remove(lists.size()-1);
Collection<List<T>> headCombinations=getAllCombinations(lists);
for(List<T> combination:headCombinations){
for(T tail:tailList){
LinkedList<T> longerCombination=new LinkedList<T>(combination);
longerCombination.add(tail);
result.add(longerCombination);
}
}
}
return result;
}

//kleiner test
public static void main(String... _){
List<List<String>> lists=new LinkedList<List<String>>();
for(String[] l: (new String[][]{
new String[]{"A","B","C"},
new String[]{"1","2","3"},
new String[]{"x","y","z"}})){
LinkedList<String> list=new LinkedList<String>(Arrays.asList(l));
lists.add(list);
}
System.out.println(getAllCombinations(lists));
}
[/HIGHLIGHT]
moment, ich bastle mal eine iterable-version.

 

[Ebenius]

moment, ich bastle mal eine iterable-version.

Scheint sich um nen längeren Moment zu handeln.

Ebenius

 

[0x7F800000]

Scheint sich um nen längeren Moment zu handeln.

bububububu (-.-)


Ich hatte was zu tun^^ Und ja, ich hab etwas länger gebraucht
Ist am ende irgendwie doch abartig geworden
Ich hab ziemlich viel Zeit damit gekillt, Kartesisches Produkt von abzählbaren also Iterable Mengen zu machen, aber ich bin an diesem komischen diagonal-verfahren irgendwie kläglich gescheitert

Egal. Für endliche mengen ist auch diese Lösung imho ganz akzeptabel:
[HIGHLIGHT="Java"]
/*
* example: buckets=[[A1,A2,..Aa],[B1,B2,..Bb],...,[X1,X2,..Xx]]
* the method will return an iterable that allows to iterate over all elements from Cartesian product
* [A1,A2,..Aa]x[B1,B2,..Bb]x[X1,X2,..Xx]
* that means it returns an iterator with all combinations:
*
* [A1,B1,...X1]
* [A2,B1,...,X1]
* [A3,B1,...,X1]
* ...
* [A1,B2,...,X1]
* [A2,B2,...,X1]
* ...
* [Aa,Bb,...,Xx]
*
* @param sets: ordered List of collections of <T> structures
* @return: Iterable of List<T> with all elements of cartesian product
*/

public static <T> Iterable<List<T>> finiteCartesianProduct(final List<Collection<T>> sets){
return new Iterable<List<T>>(){
private long size=1;
{
for(Collection<T> set:sets)size*=(long)set.size();
}
@Override
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>(){
long counter=0;
ArrayList<T> currentValues=new ArrayList<T>(sets.size());
ArrayList<Iterator<T>> iterators=new ArrayList<Iterator<T>>(sets.size());
{
for(Iterable<T> set:sets){
Iterator<T> it=set.iterator();
iterators.add(it);
if(it.hasNext()){
//if not, then the size is 0, hasNext is never true, set empty
currentValues.add(it.next());
}
}
}

@Override
public boolean hasNext() {
return counter<size;
}

@Override
public List<T> next() {
List<T> result=new LinkedList<T>(currentValues);
counter++;
increment(0);
return result;
}

private void increment(int i){
if(iterators.get(i).hasNext()){
currentValues.set(i,iterators.get(i).next());
}else{
iterators.set(i,sets.get(i).iterator());
currentValues.set(i,iterators.get(i).next());
if(i<iterators.size()-1){
increment(i+1);
}
}
}

@Override
public void remove() {
throw new UnsupportedOperationException("impossible to change combination set");
}
};
}
};
}

//kleiner test
public static void main(String... _){
List<Collection<String>> lists=new LinkedList<Collection<String>>();
for(String[] l: (new String[][]{
new String[]{"A","B","C","D","E"},
new String[]{"1","2","3","4"},
new String[]{"x","y","z","w","v"}})){
LinkedList<String> list=new LinkedList<String>(Arrays.asList(l));
lists.add(list);
}
for(List<String> x:finiteCartesianProduct(lists)){
System.out.println(x);
}
}
[/HIGHLIGHT]

 

[0x7F800000]

Zu meiner Verteidigung:
Der code mag zwar etwas zu breit erscheinen, aber die Lösung mit iterable ermöglich es, alle Elemente nacheinander aufzuzählen, ohne die alle aufeinmal in den Speicher packen zu müssen (was bei solchen Kombinatorischen Fragen sehr schnell unmöglich wird).

 

[Ebenius]

Ich wollte nur dass das Thema wieder hochkommt. Ist ja gelungen, ge?

Ebenius

 

[0x7F800000]

Ja, durchaus^^
Jetzt hast du aus mir eine halb fertige Lösung für endliche Mengen rausgeprügelt ^^
*Ebenius ist schuld, haben das alle gehört?*

nene, scherz... ich bin einfach unfähig, da gibt keine entschuldigung

Aber das mit abzählbaren mengen liefere ich noch nach irgendwann mal, wenn's notwendig wird, hab mich irgendwie festgefahren im Moment

 

[Ebenius]

"Schuld" ist mein zweiter Vorname; frag meine Freundin.

Ebenius

 

[0x7F800000]

"Schuld" ist mein zweiter Vorname; frag meine Freundin.

lol, bei solchen konflikten sollte man nicht die energie mit schuldzuweisungen verschwenden, sondern konstruktiv nach einer Lösung suchen, ich dachte die Informatiker wüssten das automatisch, die lösen doch dauernd was^^
Naja, vielleicht ist deine Freundin ja wesentlich komplizierter als Java, ka...

 

[0x7F800000]

Jetzt geht's hier mit dem Offtopic los, omg^^

 

[Ebenius]

Warum eigentlich eine iterative Lösung? Ist das in irgendeinem Sinn besser? Die Frage meine ich ernst, da fehlt mir sicher einige Kenntnis. Ist mein Ansatz oben nicht so toll, oder warum noch so viele Alternativen?

Ebenius

 

[0x7F800000]

Warum eigentlich eine iterative Lösung? Ist das in irgendeinem Sinn besser?

Wo ist denn bei meinen Lösungen etwas iterativ? Bei zweiten Methode kommen nur ein paar schleifen in den Initialisierern vor, danach klickt sich nur noch der Iterator durch alle kombinationen. Das ist so "halb iterativ", das inkrementieren könnte man auch iterativ umschreiben (bei der Variante 2)

Ist mein Ansatz oben nicht so toll, oder warum noch so viele Alternativen?

Ich hab deinen Ansatz da oben nicht im detail nachvollzogen, aber da machst du im Endeffekt dasselbe wie meine erste Variante: du gibst die menge mit allen Kombinationen aus. Meine Variante ist halt rekursiv[edit] & mit generics. Ich hab wohl zuviel Prolog programmiert, das mit schleifen umzusetzen finde ich ungemein schwieriger^^

Aber deine und meine erste Varianten sind "in der Praxis" nicht Anwendbar, weil zum speichern der gesammten Liste extremst viel Speicher benötigt wird, das endet immer mit einer OutOfMemoryException (oder wie die auch heißt).

Mit diesem Problem wurde man hier schon paar mal konfrontiert, der Vorschlag mit Iterable kam letztendlich von Marco13 bei der berechnung der Potenzmenge (die auch explosionsartig anwächst). Dann werden die Elemente häppchenweise ausgegeben, einer nach dem anderen, und gleich wieder vergessen. Alle gleichzeitig will man normalerweise auch nicht haben, sondern jede Kombination einzeln.

[edit]
Hehe, du bist ja Mod^^ Seit wann denn das? Neulich erst, oder habe ich diese erstaunliche Tatsache bisher irgendwie übersehen? (ó_Ò)?

 

[Ebenius]

Aber deine und meine erste Varianten sind "in der Praxis" nicht Anwendbar, weil zum speichern der gesammten Liste extremst viel Speicher benötigt wird, das endet immer mit einer OutOfMemoryException (oder wie die auch heißt).

For the records: OutOfMemoryError

Mit diesem Problem wurde man hier schon paar mal konfrontiert, der Vorschlag mit Iterable kam letztendlich von Marco13 bei der berechnung der Potenzmenge (die auch explosionsartig anwächst). Dann werden die Elemente häppchenweise ausgegeben, einer nach dem anderen, und gleich wieder vergessen. Alle gleichzeitig will man normalerweise auch nicht haben, sondern jede Kombination einzeln.

Genau den Teil hatte ich irgendwie im Thema verpasst; danke für die Aufklärung.

Ebenius

 

[Pfaeff]

Das Problem mit dem Speicherverbrauch ist auch genau das, welches ich bei deiner rekursiven Variante hatte. Ich weiß nicht, ob es hauptsächlich an der Rekursion liegt, oder an der Tatsache dass die Liste zu groß wird. Mir reicht es nämlich wirklich nur ein Element zur Zeit abzuhandeln. Ich werde mir deine ?halb?-iterative Methode (langes teil) mal genauer anschauen Vielen Dank!

mfg

 

[0x7F800000]

Das Problem mit dem Speicherverbrauch ist auch genau das, welches ich bei deiner rekursiven Variante hatte. Ich weiß nicht, ob es hauptsächlich an der Rekursion liegt, oder an der Tatsache dass die Liste zu groß wird. Mir reicht es nämlich wirklich nur ein Element zur Zeit abzuhandeln. Ich werde mir deine ?halb?-iterative Methode (langes teil) mal genauer anschauen

exakt dafür wurde es geschrieben

 

[Pfaeff]

Es dauert zwar immernoch tierisch lange (liegt aber eher am durchgehen der Schleife und der Tatsache dass es so viele Elemente werden) aber es funktioniert ansonsten super, vielen dank

 

[0x7F800000]

Tierisch lange? hmm... schade...
Kannst du den codeausschnitt grad posten?

 

[Pfaeff]

Ich glaube die Bestimmung der Permutationen selbst dauert nichtmal so lange. Es liegt einfach daran, dass es schon ein bissl dauert hundertmillionen Möglichkeiten durchzugehen Ich mache es also momentan so, dass ich nicht das beste Element suche, sondern das nehme was für meine Zwecke gut genug ist Würde ich das optimierter haben wollen, müsste ich meinen Ansatz komplett umstoßen und dann wirds kompliziert, so passt das schon

mfg

 

[0x7F800000]

Dann ist es aber ziemlich gemein zu behaupten mein code wäre lahm

was machst du denn überhaupt, falls kein betriebsgeheimnis?

 

[Pfaeff]

Meine Idee war, ein Programm zu schreiben, welches nach Eingabe einer Melodie ein möglichst optimal spielbares Pattern für Gitarre/Bass/... ausgibt. Hierzu habe ich eine Bewertungsfunktion geschrieben (Ich dachte zuerst daran einen genetischen Algo zu machen). Dann berechne ich alle Möglichkeiten(dank deines/euren codes) die es gibt, diese Melodie zu spielen und ermittle die beste. Nun habe ich festgestellt, dass es einfach reicht, den erstbesten über einen bestimmten Wert zu nehmen. Vermutlich lässt sich das ganze Problem auch 1000x schneller und eleganter lösen (ich hatte da auch schon einige Ideen), aber dann wirds vermutlich sehr kompliziert.

Für die Musiker unter euch, hier mal eine Beispielausgabe (Eingegeben wurden lediglich die Töne, nicht wo sie gespielt werden, das ist wie gesagt das was das Programm ermittelt):

C-Dur Tonleiter: 
Anzahl möglicher Riffs: 21600
Wert: 0.708860759493671
E|------------------
H|--------------0-1-
G|----------0-2-----
D|----0-2-3---------
A|--3---------------
E|------------------

Blues Tonleiter (A): 
Anzahl möglicher Riffs: 2764800
Wert: 0.5116279069767442
E|----------------------5-8-
H|------------------5-8-----
G|--------------5-7---------
D|----------5-7-------------
A|------5-7-----------------
E|--5-8---------------------

Worst Cases (sprich absolut unspielbar) wären diese hier:

C-Dur Tonleiter: 
Anzahl möglicher Riffs: 21600
Wert: 0.08763693270735523
E|------------------
H|------------------
G|------------2-----
D|----0---3---------
A|--3---------------
E|------12---15---19-20-

Blues Tonleiter (A): 
Anzahl möglicher Riffs: 2764800
Wert: 0.08516129032258064
E|--------------------3-----
H|----------------3---------
G|------------2-----------17-
D|------0-2-------------19---
A|--0---------------19-------
E|----8-----15---20-----------

mfg

 

[0x7F800000]

Oh-oh, jetzt gibt's einen Kandidaten für Namenskollision mit prog-metal und math-metal:
java-programmierter-math-metal^^ Ich hab kA von musik, ich dachte eigentlich die Leute machen's irgendwie halbwegs instinktiv

 

[Pfaeff]

Die Idee stand daraus, dass diverse Musik Programme es einfach nicht hinbekommen die Melodien einigermaßen spielbar darzustellen. Also hab ich mir eine Methode ausgedacht die zwar Quick&Dirty ist, aber ganz gut zu funktionieren scheint. Das passiert wenn man beide Hobbies unter einen Hut bringen will

mfg
Der Begründer von java-programmierer-math-metal

 

[Pfaeff]

Angenommen ich hätte n Schleifen, wobei diese nur jeweils zweimal durchlaufen werden. sprich:

for (int a=0; a<2; a++) {
for (int b=0; b<2; b++) {
for (int c=0; c<2; c++) {
}
}
}

sprich es gibt 2^n Kombinationen

Gibt es hierfür einen einfacheren Algorithmus? (ist ja doch um einiges spezieller)

 

[0x7F800000]

Das wiederum hört sich nach Potenzmenge an, oder?

Prinzipiell steht HIER schon ziemlich viel zu dem Thema. Aber ich habe hier noch ein Buch zu Skiena, ich schau da mal kurz rein, vielleicht komme ich auf weitere tolle ideen...

Wenn du das gebrauchen könntest, schreibe ich gleich nochmal so eine methode die ein Iterable-Konstrukt liefert, der alle teilmengen abzählt... Ich will's eh haben für alle Fälle Aber ich meine, dass Marco13 schon irgendwo so etwas gebaut hat (womöglich hat er aber auch nur die Idee erwähnt) :-?

 

[Marco13]

Ich hatte nur in einem anderen Thread, als es darum ging, ein Iterable zu basteln, erwähnt, dass das ziemlich trivial ist, wenn man erstmal die berühmte Bijektion von den natürlichen Zahlen auf die Elemente der Ergebnismenge hat. Das iterable liefert dann ja nur einen Iterator wie

Iterator iterator = new Iterator()
{
    int index = 0;
    void remove() { /*nö*/ }
    boolean hasNext() { return index < bijektion.getNumElements(); }
    Element next() { return bijektion.get(index++); }
}

 

[Pfaeff]

Potenzmenge ist fast richtig

angenommen ich habe a und b (boolean) und möchte alle kombinationen, dann sind das ja
(0,0), (0,1), (1,0), (1,1)
die Potenzmenge wäre aber doch (wenn man als Menge {1, 0} nimmt:
(0), (1), (0,1), (1,0)
wenn ich mich jetzt nicht irre.

Vielen Dank auf jedenfall für für die Mühe, irgendwie stellen sich mir solche Fragen in letzter Zeit häufiger .
Dass es dafür noch kein Sprachkonstrukt in java gibt...

 

[0x7F800000]

Das was du angeschrieben hast, sind werte der Indikatorfunktion, die auf der potenzmenge definiert ist. Wenn du genau hinguggst, dann siehst du, dass es einfach nur binäres Hochzählen ist:
00=0
01=1
10=2
11=3

und so weiter... genauso hat Marco13 in diesem beitrag die potenzmenge zusammengebaut. Du musst nicht einmal die mengen an sich bauen, du brauchst wirklich nur noch zu zählen...

 

[Pfaeff]

Tatsächlich also vereinfacht es das Problem doch sehr stark (Hätte ich auch selbst drauf kommen können, aber man denkt entweder zu kompliziert oder nicht genug )
Vielen Vielen Dank nochmal an alle!