Sortieren mit Bedingungen

[ni-ko-o-kin]

Hallo!

Ich habe eine endliche Anzahl an Elementen die ich aneinander reihen will. Aber bestimmte Elemente dürfen nicht neben anderen Elementen stehen.

zb(pseudo-code):
Element_01.Anzahl = 2
Element_02.Anzahl = 1
Element_03.Anzahl = 3

liste.länge = 6
zb:
liste = [1,1,2,3,3,3]
oder
liste = [1,2,3,1,3,3]
usw

Das heißt, es gibt Zwei Elemente vom 'Element_01' und Ein Element von 'Element_02' usw. Insgesamt gibt es dann 6 Elemente.

Da gibt es jetzt viele unterschiedliche Möglichkeiten diese Elemente anzuordnen. Wieviele Möglichkeiten es gibt hat man ja schon in der Schule mit der Kombinatorik gelernt, aber nicht wie man alle möglichkeiten anzeigen lassen kann.

Weiters gibt es noch Bedinungen:
zb
Element_01 darf neben sich selbst und neben Element_02 stehen
Element_02 darf neben allen elementen stehen.
Element_03 darf neben sich selbst und dem Element_01 stehen.

Wie kommt man am schnellsten zu allen Möglichkeiten?
Habt ihr irgendwelche Hinweise wie ich das lösen kann?

Grüße,
niko
.[/code]

[cofi]

http://docs.python.org/library/functions.html#sorted

Da musst du wohl deine eigene `cmp` Funktion schreiben.

[Panke]

Ich glaube, damit ist es nicht getan.

[numerix]

Da gibt es jetzt viele unterschiedliche Möglichkeiten diese Elemente anzuordnen. Wieviele Möglichkeiten es gibt hat man ja schon in der Schule mit der Kombinatorik gelernt, aber nicht wie man alle möglichkeiten anzeigen lassen kann.

Code: Alles auswählen

>>> from itertools import permutations
>>> a = [1,1,2,3,3,3]
>>> ways = sorted(set(permutations(a)))

Das musst du dann noch auf die einzuhaltenden Bedingungen prüfen.

[ni-ko-o-kin]

vielen dank für die antworten. bin am ausprobieren....

niko
.

[ni-ko-o-kin]

Code: Alles auswählen

from itertools import permutations
a=[1,1,2,3,3,3,1,1,2,3,3,3]
ways = sorted(set(permutations(a)))
print ways

Bei der doppelten Menge an Elementen dauert das ganz schön lange. Es gibt ja dann auch einige(!) Lösungen. Aber eigentlich genügt mir eine gültige Lösung (wo alle Bedinungen erfüllt werden).

Da lautet meine Frage dann: Dauert es länger wenn ich eine Permutation nach der anderen Abfrage ob sie alle Bedinungen erfüllt oder wenn ich eine Funktion schreibe die aus, wahrscheinlich, recht vielen Schleifen bestehen wird, wo von Anfang an die Bedingungen geprüft werden und nur dann weitergerechnet wird wenn sie erfüllt werden. Falls bei dem letzten Element dann rauskommt dass es sich nicht ausgeht weil die Bedinungen nicht erfüllt werden können wird wieder ein Element zurückgegangen und eine andere Variantion ausprobiert. Wenn es da auch nicht geht wieder ein Element zurück, Worst Case: es muss bis zum ersten element gegangen werden.

In zukunft soll das Programm mehrere Hunderte elemente haben (welche objekte einer klasse sein werden) die bestimmte Bedinungen(pro Element 26 Bedinungen die in den Objekten als Felder gespeichert werden) haben werden. Ist das schlau oder sollten die Objekte (=Elemente) nicht 'intelligent' sein(=Die Bedingungen in sich speichern) sondern die irgendwo anders gespeichert werden?

Aber toll das es die Funktion(permutations) gibt. Hab schon begonnen gehabt so eine Funktion selbst zu programmieren. Werd aber jetzt die bereits vorhandene verwenden.

niko
.

[numerix]

In zukunft soll das Programm mehrere Hunderte elemente haben

Dass du dann mit dem jetzigen Ansatz nicht weiterkommst, müsste dir eigentlich klar sein. Was hast du denn eigentlich vor?

[ni-ko-o-kin]

Wieso komme ich mit meinem Ansatz nicht weit? Rechenzeit?

Ich habe in den letzten Monaten einen Teil von den Wiener Gründerzeithäuser nachmodelliert. Es wiederholen sich immer wieder bestimmte Fassadenelemente. Und da dachte ich mir, dass lässt sich doch mit einem Script schneller lösen.

Es soll ein 'Gebäude-Bauer' (Gründerzeithäuser) in Blender (www.blender.org) werden. Ein Element hat zum Beispiel 3m x 3m x 3m und ist ein Fassen-Element. Ein anderes ist ein Wand-Element. Usw. Der Benutzer kann diese Elemente (Mesh-Objekte in Blender) entwerfen und in Beziehung zueinander setzen. Zb.: dass ein Fassaden-Eck-Element nicht in der Mitte einer Fassade stehen darf. Oder bestimmte Fassadenelemente müssen so und so oft vorkommen. Oder die Tür muss in der Mitte sein usw. Die Höhe (Stockwerke) Breite und Länge ist vom Benutzer frei wählbar. Das ist nur mal der Anfang. Ich hab noch sehr viele Ideen.

Und das Projekt ist eigentlich nur der Auftakt zu einem etwas aufwendigeren Projekt das sich über das nächste halbe Jahr strecken wird.

niko
.

[numerix]

Wieso komme ich mit meinem Ansatz nicht weit? Rechenzeit?

Wenn du auch nur 100 Elemente hättest, gäbe es schon rund 10^158 Permutationen. Aufgrund der identischen Elemente sind es zwar am Ende (möglicherweise sogar ganz erheblich viel) weniger, aber der von mir gezeigte "Ansatz" erzeugt ja erst einmal ALLE Permutationen.

Um mit so vielen Elementen zurecht zu kommen, wirst du dir einen intelligenteren Ansatz als diese "brute-force"-Methode überlegen müssen, die nur für ziemlich kleine Element-Anzahlen brauchbar ist.

[ni-ko-o-kin]

Das war ja mein ursprüngliche Frage: wie schaut so eine intelligente Methode aus? Gibt es da einen Algorithmus der für so was gedacht ist?
Außerdem brauch ich nur eine Lösung die alle Bedingungen erfüllt. Sorted kann sicher auch nur eine Permutation ausgeben, oder?

Anfänglich hab ich ja versucht diese Permutation-Funktion selbst zu schreiben. Der Rechenaufwand war aber sehr hoch.

niko
.

[Hyperion]

Klingt für mich nach einem erweiterten Färbeproblem (Wiki Artikel)

Insofern vermute ich mal, dass es genauso NP vollständig ist. Also praktisch nicht lösbar.

[numerix]

Das war ja mein ursprüngliche Frage: wie schaut so eine intelligente Methode aus? Gibt es da einen Algorithmus der für so was gedacht ist?

Naja, deine ursprüngliche Frage war auch mit einem Beispiel mit 6 Elementen verknüpft. Hättest du gleich gesagt, dass es um >100 geht, hätte ich den Vorschlag mit Permutationen gar nicht erst gemacht.

Trotz deiner Beschreibung (Fassaden etc.) habe ich noch nicht verstanden, warum du alle denkbaren "echten" Permutationen (d.h. ohne Dubletten) brauchst und inwiefern solche Größenordnungen zustande kommen. Genügt es denn nicht, beim Einfügen jedes neuen Elements dem "Bauherrn" zu sagen, an welche Stellen er es einfügen darf?

[ni-ko-o-kin]

Ich seh schon: Falls ich sehr viele Elemente hab und die Bediungengen haben dann wird es viele Kombinationen geben die nicht funktionieren aber nur wenige die gültig sind. hm......

Aber es müssen doch schon viele, viele Menschen vor mir so ein Problem gehabt haben und eine Lösung gefunden haben???

niko
.

[ni-ko-o-kin]

Naja, deine ursprüngliche Frage war auch mit einem Beispiel mit 6 Elementen verknüpft. Hättest du gleich gesagt, dass es um >100 geht, hätte ich den Vorschlag mit Permutationen gar nicht erst gemacht.

Sorry. My Bad!

Trotz deiner Beschreibung (Fassaden etc.) habe ich noch nicht verstanden, warum du alle denkbaren "echten" Permutationen (d.h. ohne Dubletten) brauchst und inwiefern solche Größenordnungen zustande kommen. Genügt es denn nicht, beim Einfügen jedes neuen Elements dem "Bauherrn" zu sagen, an welche Stellen er es einfügen darf?

Es gibt halt ganz viele Möglichkeiten:
1: ecke
2: fassadenteil
3: tür
zb
1-2-2-2-2-2-3-2-1
oder
1-2-3-2-2-2-2-2-1
usw
[edit] das ding geht dann in 3-Dimensionen, deswegen so viele elemente

und es gibt dann zb noch
4: fenster
5: fassdenteil_x (der zb nur neben fassadenteil y stehen darfs)
6: fassadenteil_y
usw

Ich dachte am Anfang, dass ich alle Möglichkeiten brauch, aber es hat sich herausgestellt dass ich nur eine gültige brauch.



Kennt ihr das Spiel Roller Coaster Tycoon? Da kann man seine Bahnen Auto-vervollständigen lassen:
http://www.youtube.com/watch?v=EMrXLY-addY
Bei dem Video findet er zwar keine Lösung aber im Spiel funktioniert das recht fein.Von der Idee her, sollte mein Programm so etwas werden.

niko
.

[Hyperion]

Aber es müssen doch schon viele, viele Menschen vor mir so ein Problem gehabt haben und eine Lösung gefunden haben???

Hast Du meinen Beitrag gesehen und mal nachgeforscht? Wie gesagt sieht es für mich auf den ersten Blick wie ein Färbeproblem aus. Und damit wäre es eben NP.

[ni-ko-o-kin]

Ja, hab ich gesehen und gelesen, aber verstanden hab ich das nicht. Aber wenn du meinst dass es ein nicht lösbares Problem ist versteh ich das auch nicht. Weil wir ja schon eine Lösung gefunden haben, nur ist leider der Zeitaufwand zu hoch. Also kann es doch sein, dass es auch eine Lösung gibt wo das schneller geht.

Vielen Dank mal an Alle die mir weitergeholfen haben. Ich werd weiter versuchen dafür eine Lösung zu finden. Vielleicht brauch ich einen anderen Ansatz an das Problem.

niko
.

[Hyperion]

Weil wir ja schon eine Lösung gefunden haben, nur ist leider der Zeitaufwand zu hoch. Also kann es doch sein, dass es auch eine Lösung gibt wo das schneller geht.

Das ist ja der Witz an NP-Vollständigkeit Natürlich wird es eine Lösung geben - aber Du kannst sie nicht berechnen.

Guck mal hier:
http://de.wikipedia.org/wiki/Problem_de ... sreisenden

Das dürftest Du verstehen

Wie gesagt, ich will mich nicht zu 100% festlegen, ob Dein Problem in diese Klasse fällt. Es sieht aber auf den flüchtigen Blick so aus.

[ni-ko-o-kin]

ach so........... hm.......

Danke! Werd ich mir morgen durchlesen!

niko

[numerix]

Weil wir ja schon eine Lösung gefunden haben, nur ist leider der Zeitaufwand zu hoch.

Und damit ist es - sofern es überhaupt eine gewesen wäre - dann auf jeden Fall auch keine Lösung mehr ...

[Panke]

passend dazu: http://cacm.acm.org/magazines/2009/9/38 ... m/fulltext