permutation einer liste

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
dracana
User
Beiträge: 22
Registriert: Donnerstag 11. Oktober 2007, 10:49

guten tag.

hi, ich sitzte gerade an einem schulprojekt.
Ein roboter soll verschiedene stationen anlaufen und braucht bestimmte zeiten für verschiedene wege, dies alles hab ich in klassen programmiert. ich hab eine klasse roboter und eine klasse stationen erstellt, mit der klasse stationen kann ich unendlich viele stationen in unterschiedlichen abständen erstellen (alles nur theoretisch in der konsole eine GUI kommt noch)...

dieser roboter soll nun alle möglichen varianten durchgehen und die zeit messen... also ich bin jetzt so weit, dass die stationen aufgelistet werden und der roboter diese liste abläuft...

also die liste sieht so aus [statio1,statio2,statio3,...,statio'x'] so, nun läuft der roboter sie in der reihenfolge ab, aber er soll auch alle anderen varianten laufen... nunja also hier mal ein beispiel:

wenn ich die liste [a,b,c] habe soll diese liste diese ganzen formen annehmen:

abc,acb,bac,bca,cab,cba

ich habe mich lange mit dem Problem beschäftigt und habe keinen algorithmus programmieren können, der dieses problem löst höchstens eine liste mit 4 einträgen konnte mein algorithmus lösen... bei 5 fing er schon an varianten zu doppeln... ich weiß dass man so einen algorithmus auch rekusiv aufbauen kann, oder sollte.^^ Wie mache ich das... bzw wie programmier ich sowas? ich habe wirklich schon ne menge ausprobiert und bin mit meinem latein am ende.

ich freue mich auf anworten und anregungen die mir weiterhelfen könnten :)

mit freundlichem gruß, thorte

ps: mit der groß und kleinschreibung hab ich es nicht so, ich hoffe ihr verzeiht mir dies =)
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Achtung, Spoiler:
http://docs.python.org/library/itertool ... rmutations

Bau dir, wenn du es denn selbst machen willst, erstmal ne Funktion fürs Karthesische Produkt, daraus kannst du das dann ableiten, oder sogar die Permutations-Funktion mit der Produkts-Funktion implementieren.

Btw:
Wenn du den Algo für 3 und für 4 Elemente bauen kannst, dann kannst du doch einfach jeden Fall auf den Fall der 3 Elemente zurück führen.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

dracana
User
Beiträge: 22
Registriert: Donnerstag 11. Oktober 2007, 10:49

hallo =)

vielen dank für eure schnelle hilfe, und ich bin fündig geworden. ich hab hier im forum nach permutation gesucht aba da keiner sein thema direkt so bannant hat, nichts gefunden, aba durch eure links jetzt schon... nun habe ich dieses code gefunden:

Code: Alles auswählen

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]

for p in all_perms(['a','b','c']):
    print p
dieser code funktioniert genau so wie cih ihn brauche allerdings würde ich mich freuen, wenn mir jmd diese letzte zeile

Code: Alles auswählen

 yield perm[:i] + str[0:1] + perm[i:]
erklären könnte :S ich würd nämlich die funktionsweise nämlich schon gerne verstehen... ich bau in meine scripte kein quelltext ein den ich nicht verstehe ^^
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Code: Alles auswählen

In [13]: def foo():
   ....:        yield "hello"
   ....:        yield "world"
   ....:                     

In [14]: f = foo()

In [15]: f
Out[15]: <generator object at 0x20f3e18>

In [16]: f.next()
Out[16]: 'hello'

In [17]: f.next()
Out[17]: 'world'

In [18]: f.next()
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)

/home/dasich/<ipython console> in <module>()

StopIteration:
Antworten