Rekursive Funktion

[red_dust]

Hallo ich habe mehr oder weniger ein mathematisches Problem und komme einfach nicht auf eine elegante Lösung.
Es gibt in einer Liste N Einträge, jeder der N Einträge hat eine Unterliste mit L Einträgen. Jeder Eintrag soll ein mal mit jedem anderen gelistet werden

Bsp. [[A,[a1]], [B,[b1,b2]], [C,[c1,c2]]]

Daraus soll die Liste:
[a1,[a1,b1],[a1,b2],[a1,c1],[a1,c2],[a1,b1,c1],[a1,b1,c2], [a1,b2,c1], [a1,b2,c2],b1, [b1,c1],[b1,c2],b2,[b2,c1],[b2,c2],c2]

generiert werden. Das Programm soll aber für eine beliebige Anzahl von N Einträgen funktionieren.
Ich denke mit einer rekursiven Funktion könnte man dem Herr werden, aber ich komme einfach nicht drauf wie diese aussehen muss

Seit zwei Tagen versuche ich jetzt schon eine Lösung zu programmieren, musste aber jeden Code wieder löschen…
Mein letzter Stand:

Code: Alles auswählen

def try3():
    a=['a1', 'a2', 'a3']
    b=['b1','b2']
    c=['c1', 'c2', 'c3']
    savList=[['A', a],['B', b], ['C', c]]
    entryList=[]
   
    timesToIterate=len(savList)
    #iterate over A, B, C
    for iConfigs in range(timesToIterate):
        #iterate over entries of A, B, C
        for firstSa in range(len(savList[iConfigs][1])):
            #add every single entry of A, B, C solely
            entryList.append(savList[iConfigs][1][firstSa])
            #if more than one entry in list (more than A) add entries of B and C and...
            if timesToIterate>1:
                for nextConfig in range(1,len(savList)-1):
                    #number of entries per Config A:3, B:2, C:3
                    numberSAsPerConfig=len(savList[nextConfig][1])
                    #do only, if not the last (this case C)
                    if iConfigs<timesToIterate-1:
                        #first add entry from first entry (A, so add a1)
                        appendTemp.append(savList[iConfigs][1][firstSa])
                        #than add all other configs
                        ...??recursive funtion here??
                        ...
                                    
                        entryList.append(appendTemp)
                  
    print str(entryList)

Gibt es hier Mathematik oder Programmier-Genies die mich auf die richtige Fährte bringen können bevor mein Hirn zu Staub zerfällt??

Vielen Dank

[cofi]

Geh doch bitte mal genau auf die Abbildungsfunktion ein. Aus deinem Beispiel werde ich auf Anhieb nicht schlau und sie aus deinem Code herauszupopeln fuehrt effektiv dazu, dass man auf deinen Gedanken weiterfaehrt.

Und geh doch bitte mal auf das "grosse Problem" ein, das du loesen willst. Das Beispielergebnis sieht fuer mich nach einer katastrophalen Datenstruktur fuer jeden Zweck aus.

[BlackJack]

@red_dust: Ich würde mich cofi anschliessen, dass die Datenstruktur vom Beispielergebnis nicht gut ist. Die ist unregelmässig, so etwas sollte man vermeiden, denn unregelmässige Datenstrukturen bedeuten in der Regel zusätzlichen Quelltext und Fallunterscheidungen für die Elemente deren Struktur aus der Reihe tanzt. In diesem Fall sind das die Einzelelemente, die im Gegensatz zu allen anderen Elementen der äusseren Liste selbst keine Listen sind.

Ich habe mal versucht die Struktur hinter dem Beispiel zu erraten und bin mir fast sicher, dass am Ende vor dem letzten Element c2 ein c1 fehlt, kann das sein?

Denn dann möchtest Du die Vereinigung der Kreuzprodukte der n-elementigen Permutationen ohne Ordnung (also (a, b) ist das gleiche wie (b, a)) der N Ausgangsmengen, wobei n die Werte von 1 bis N annimmt. Oder in Quelltext ausgedrückt:

Code: Alles auswählen

from itertools import permutations, product


def main():
    data = [['A', ['a1']], ['B', ['b1', 'b2']], ['C', ['c1', 'c2']]]
    xs = [tuple(x[1]) for x in data]
    result = list()
    for i in xrange(1, len(data) + 1):
        for ps in set(tuple(sorted(x)) for x in permutations(xs, i)):
            result.extend(product(*ps))
    result.sort()
    print result


if __name__ == '__main__':
    main()

Ergebnis: [('a1',), ('a1', 'b1'), ('a1', 'b1', 'c1'), ('a1', 'b1', 'c2'), ('a1', 'b2'), ('a1', 'b2', 'c1'), ('a1', 'b2', 'c2'), ('a1', 'c1'), ('a1', 'c2'), ('b1',), ('b1', 'c1'), ('b1', 'c2'), ('b2',), ('b2', 'c1'), ('b2', 'c2'), ('c1',), ('c2',)]

[red_dust]

Ups, sorry ich hätte dazu sagen sollen dass die Reihenfolge in der Ausgabeliste egal ist.
@BlackJack: Super! Trotz in die Glaskugel schauen, hast du mein Problem exakt erkannt. Permutation ist die mathematische Vorgehensweise die ich gesucht habe. Ein Ärger dass ich selbst nicht drauf gekommen bin, ich programmier leider meist drauf los ohne mir vorher eine theoretische Lösung zu überlegen