Kombinatorik - Sämtliche Routen-Kombinationen erstellen

[robocode]

Hallo liebe Gemeinde,
ich stehe vor folgendem Problem:

Ich habe eine Liste mit Koordinatenpunkten, die zu einer Route verbunden werden sollen. Die Liste besitzt dabei einen Startpunkt A, einen Zielpunkt B und Zwischenpunkt ZP(i). Dabei möchte ich mir alle Routenkombinationen nach Länge sortieren lassen und danach ausgeben. Wie ich die Distanz zwischen zwei Punkten berechne ist in diesem Fall trivial, mir geht es nur um die verschiedenen möglichen Routenkombination. Hier folgendes kleines Beispiel mit zwei Zwischenpunkten:

A: Startpunkt
B: Zielpunkt
ZP(i): Zwischenpunkt i, Beispiel beeinhaltet die zwei Zwischenpunkte ZP1 und ZP2

mögliche Routen:
A -> B
A -> ZP1 -> B
A -> ZP2 -> B
A -> ZP1 -> ZP2 -> B
A -> ZP2 -> ZP1 -> B


Der Kern meiner Frage lautet, wie ich Python alle möglichen Routen zusammenstellen lassen kann wenn ich 1 bis n Zwischenpunke habe.

Vielen Dank!
robocode

[Hyperion]

Du könntest Dir mal ``itertools.permutation`` angucken! Du musst das für jede Anzahl zwischen 1 und der Anzahl an Zwischenhalten durchführen und die Ergebnisse sammeln. Start- und Endpunkt lässt Du dabei natürlich weg, da diese ja implizit immer gegeben sind.

[robocode]

Hallo Hyperion, vielen Dank für die schnelle Antwort letzte Woche. Ich hab viel rumprobiert und bin auf folgenden Code gekommen:

Code: Alles auswählen

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n) 
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return
            

liste1=[1,2,4]
Kombinationen=[]
k=len(liste1)+1
for i in range(1,k):  
  Kombinationen.append(list(permutations(liste1,i))) 
  
print Kombinationen 

Ausgabe: [[(1,), (2,), (4,)], [(1, 2), (1, 4), (2, 1), (2, 4), (4, 1), (4, 2)], [(1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1)]]


Ich schaffe es jedoch noch nicht, alles was oben steht in eine Funktion zu schreiben, der nur noch eine Variable übergeben werden muss (also die liste1).
Am Ende würde ich gerne nur noch z.B. permutations(liste1) ausführen lassen. Hat mir da jemand einen Gedankenanstroß?

[BlackJack]

@robocode: Warum verwendest Du nicht `itertools.permutations()`?

[robocode]

Weil ich momentan noch mit Python 2.5 arbeiten muss

[Hyperion]

Guck Dir mal Brownie an! Das war mal genau für solch arme Menschen gedacht

[robocode]

Würds gerne erstmal so versuchen, hab ja schon bisschen was hinbekommen. Könnt ihr mir nen Tipp geben, wie ich den Teil

Code: Alles auswählen

liste1=[1,2,4]
Kombinationen=[]
k=len(liste1)+1
for i in range(1,k):  
  Kombinationen.append(list(permutations(liste1,i)))
 
print Kombinationen 

mit in def permutations(iterable) packen kann?

[EyDu]

Warum sollte man das tun wollen? Schreib dir eine Funktion welche permutations verwendet und fertig.

[Hyperion]

@robocode: Wir haben Dir ja nun mehrere Möglichkeiten aufgezeigt, wie Du eine fertige ``permutation``-Funktion nutzen kannst. Wieso Du die nicht nutzt, hast Du uns nicht genannt. Es bleibt aber eigentlich nur eine (plausible) Option: Das ganze ist eine Hausaufgabe. Und da kauen wir hier einfach nichts vor

Und nur mal so: Wenn man schon abschreiben will, kann man auch mal im Netz nach dem Code dazu gucken (Insbesondere bei Brownie tippe ich mal auf eine reine Python Implementierung)

[robocode]

@EyDu: Danke für den Tipp, ich hab irgendwie gar nicht daran gedacht einfach eine neue Funktion zu definieren und damit einfach permutations aufzurufen.

Habs jetzt so gelöst

Code: Alles auswählen

def perm_iter():    
    liste1=[1,2,4]
    Kombinationen=[]
    k=len(liste1)+1
    for i in range(1,k):  
        Kombinationen.append(list(permutations(liste1,i)))
    print Kombinationen 
    

perm_iter()

Danke auch an Hyperion für den Tipp mit den itertools Codebausteinen. Ich nutze doch die fertige permutation Funktion, halt nur die längere Version die auch für Python 2.5 nativ geht.
@Hyperion: Ist keine Hausaufgabe, wollte nur wissen ob es einen Weg gibt die Schleife die ich jetzt über die Funktion perm_iter() aufrufe auch direkt in der permutations-Funktion zu implementieren.

[robocode]

Ich hab mit meinem Code beim ausführen teilweise Probleme. Wenn ich untenstehenden Code ausführe kommt erhalte ich korrekterweise als Ausgabe [[(3,), (4,)], [(3, 4), (4, 3)]] . Manchmal kommt jedoch folgende Fehlermeldung:

File "::PythonSkript", line 35, in <module>
File "::PythonSkript", line 31, in perm_iter
File "::PythonSkript", line 21, in permutations
TypeError: 'tuple' object is not callable

Wenn ich dann den Code ausschneide, das Skript neu kompiliere, den Code wieder einfüge und dann kompiliere scheint es wieder zu gehen. Hat jemand eine Idee woran das liegen könnte?

Code: Alles auswählen

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n) 
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else: 
            return
            

def perm_iter(statement_string):          #Statement-String der eingelesen wird"
  Kombinationen=[]
  k=len(statement_string)+1
  for i in range(1,k):  
    Kombinationen.append(list(permutations(statement_string,i))) 
  print Kombinationen 
   
statement_string=[3,4] 
perm_iter(statement_string)  

[Hyperion]

"Manchmal" klingt komisch und gibt es eigentlich nur bei Multithreading in dieser Art und Weise bzw. auch bei externen Abhängigkeiten, die sich ändern. Ansonsten *müssen* Quellcodeänderungen ursächlich sein!

Die Fehlermeldung kannst Du leicht nachstellen:

Code: Alles auswählen

In [1]: t = (1, 2)

In [2]: t()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-f287f61d3e9e> in <module>()
----> 1 t()

TypeError: 'tuple' object is not callable

So eine Stelle müsste es folglich geben.

Bist Du Dir sicher, dass Du in Zeile 31 ein ``append`` und kein ``extend`` haben willst?

Die Namen sind teilweise unschön: ``perm_iter`` klingt nach einer Iterator-Funktion - ist es aber nicht! ``statement_string`` klingt nach einer Art Quellcode - in Wirklichkeit ist es aber ein Iterable von Zahlen... Grundsätzlich solltest Du keine Typinformationen in Namen codieren!

[Sirius3]

@robocode: Dein Post ist ja sehr schwammig, was Du konkret gemacht hast, dass es nicht mehr funktioniert. Deswegen rat ich einfach mal wild drauf los und vermute, dass Du globalen Code hast, der 'list', 'len', 'permutations' oder ähnliches überschreibt. Wenn die Zeilennummerierung stimmt, müßte es 'tuple' sein. Variablen wie eingebaute Funktionen zu nennen, ist nie eine gute Idee, im globalen Kontext Code auszuführen auch nicht.

[BlackJack]

@robocode: Neu kompilieren klingt auch komisch, man kompiliert Python-Quelltext ja nicht explizit, also was genau machst Du da was Du als kompilieren bezeichnest? Und führst Du das Programm auch alleinstehend aus oder das Modul aus irgendeiner IDE heraus die den Code nicht mit einem sauberen Modul-Namensraum startet?

[robocode]

Was bedeutet die Fehlermeldung "'tuple' object is not callable" konkret?

[Sirius3]

@robocode: Wie geht es konkreter als "ein Tuple kann nicht aufgerufen werden". Der Fehler tritt dann auf, wenn Du versuchst ein Tuple auzurufen, meistens weil die Variable, die Du aufrufen möchtest, nicht das ist, was Du glaubst, das es ist, sondern eben ein Tuple.

[BlackJack]

Mal als Beispiel:

Code: Alles auswählen

In [4]: (1, 2, 3)(42)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-941a16eb8d22> in <module>()
----> 1 (1, 2, 3)(42)

TypeError: 'tuple' object is not callable

Wir haben da ein Tupel (``(1, 2, 3)``) und versuchen das mit dem Argument 42 aufzurufen. Geht halt nicht.

Passiert auch manchmal wenn man eine Liste von Tupeln literal in den Quelltext schreibt und zwischen den Tupeln das Komma vergisst.