Permutationen einer Liste von Listen

Question

Ich habe eine Liste wie folgt aus:

l = [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']] 

Ich möchte ein Element aus jeder Liste wählen und kombinieren sie eine Zeichenfolge sein.

Zum Beispiel: 'AAG', 'aah', 'aar', 'aaw', 'abg', 'abh' ....

jedoch die Länge der Liste l und die Länge Jede innere Liste ist unbekannt, bevor das Programm läuft. Also, wie kann ich wollen, dass ich will?

Answer 1

Nehmen Sie eine previous solution und verwenden Sie stattdessen itertools.product(*l).

Answer 2

Ganz einfach mit itertools.product:

>>> import itertools 
>>> list(itertools.product("abc", "ab", "ghrw")) 
[('a', 'a', 'g'), ('a', 'a', 'h'), ('a', 'a', 'r'), ('a', 'a', 'w'), ('a', 'b', 'g'), ('a', 'b', 'h'), ('a', 'b', 'r'), ('a', 'b', 'w'), ('b', 'a', 'g'), ('b', 'a', 'h'), ('b', 'a', 'r'), ('b', 'a', 'w'), ('b', 'b', 'g'), ('b', 'b', 'h'), ('b', 'b', 'r'), ('b', 'b', 'w'), ('c', 'a', 'g'), ('c', 'a', 'h'), ('c', 'a', 'r'), ('c', 'a', 'w'), ('c', 'b', 'g'), ('c', 'b', 'h'), ('c', 'b', 'r'), ('c', 'b', 'w')] 

Answer 3

Wenn jemand in dem Algorithmus interessiert ist, ist hier eine sehr einfache Art und Weise Rekursion zu verwenden, um die Kombinationen zu finden:

l = [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']] 
def permu(lists, prefix=''): 
     if not lists: 
      print prefix 
      return 
     first = lists[0] 
     rest = lists[1:] 
     for letter in first: 
      permu(rest, prefix + letter) 
permu(l) 

Answer 4

Hier gehen Sie

reduce(lambda a,b: [i+j for i in a for j in b], l) 

OUT: ['aag', 'aah', 'aar', 'aaw', 'abg', 'abh', 'abr', 'abw', 'bag', 'bah', 'bar', 'baw', 'bbg', 'bbh', 'bbr', 'bbw', 'cag', 'cah', 'car', 'caw', 'cbg', 'cbh', 'cbr', 'cbw'] 

Wenn Sie wiederverwenden/regenerieren möchten:

def opOnCombos(a,b, op=operator.add): 
    return [op(i,j) for i in a for j in b] 

def f(x): 
    return lambda a,b: opOnCombo(a,b,x) 

reduce(opOnCombos, l) //same as before 
reduce(f(operator.mul), l)) //multiply combos of several integer list 

Answer 5

Rekursion

def permutenew(l): 
if len(l)==1: 
    return l[0] 
else: 
    lnew=[] 
    for a in l[0]: 
     for b in permutenew(l[1:]): 
      lnew.append(a+b) 
    return lnew 

l = [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']] 
print permutenew(l) 

Answer 6

huckepack off von JasonWoof's answer. Im Folgenden wird eine Liste erstellt, anstatt zu drucken. Beachten Sie, dass dies sehr langsam sein kann, da es viel Speicher erfordert, um die Werte zu speichern.

from __future__ import print_function 
import itertools # Not actually used in the code below 

def permu(lists): 
    def fn(lists, group=[], result=[]): 
     if not lists: 
      result.append(group) 
      return 
     first, rest = lists[0], lists[1:] 
     for letter in first: 
      fn(rest, group + [letter], result) 
    result = [] 
    fn(lists, result=result) 
    return result 

if __name__ == '__main__': 
    ll = [ [[1, 2, 3], [5, 10], [42]], 
      [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']] ] 
    nth = lambda i: 'Permutation #{0}:\n{1}'.format(i, '-'*16) 

    # Note: permu(list) can be replaced with itertools.product(*l) 
    [[print(p) for p in [nth(i)]+permu(l)+['\n']] for i,l in enumerate(ll)] 

Ergebnis

Permutation #0: 
---------------- 
[1, 5, 42] 
[1, 10, 42] 
[2, 5, 42] 
[2, 10, 42] 
[3, 5, 42] 
[3, 10, 42] 


Permutation #1: 
---------------- 
['a', 'a', 'g'] 
['a', 'a', 'h'] 
['a', 'a', 'r'] 
['a', 'a', 'w'] 
['a', 'b', 'g'] 
['a', 'b', 'h'] 
['a', 'b', 'r'] 
['a', 'b', 'w'] 
['b', 'a', 'g'] 
['b', 'a', 'h'] 
['b', 'a', 'r'] 
['b', 'a', 'w'] 
['b', 'b', 'g'] 
['b', 'b', 'h'] 
['b', 'b', 'r'] 
['b', 'b', 'w'] 
['c', 'a', 'g'] 
['c', 'a', 'h'] 
['c', 'a', 'r'] 
['c', 'a', 'w'] 
['c', 'b', 'g'] 
['c', 'b', 'h'] 
['c', 'b', 'r'] 
['c', 'b', 'w'] 

---

Im Folgenden finden Sie eine äquivalente Substitution für itertools.product(*iterables[, repeat]):

Diese Funktion entspricht den folgenden Code, mit der Ausnahme, dass die tatsächliche Implementierung baut nicht auf Zwischenergebnisse im Speicher:

def product(*args, **kwds): 
    pools = map(tuple, args) * kwds.get('repeat', 1) 
    result = [[]] 
    for pool in pools: 
     result = [x+[y] for x in result for y in pool] 
    for prod in result: 
     yield tuple(prod)