Permutation d'une liste de listes

Question

j'ai une liste comme ceci:

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

Je veux choisir un élément de chaque liste et les combiner pour être une chaîne.

Par exemple: 'AAG', 'aah', 'AAR', 'AAW', 'abg', 'ABH' ....

Cependant, la longueur de la liste l et la longueur Chaque liste interne est inconnue avant l'exécution du programme. Alors, comment puis-je faire ce que je veux?

Answer 1

Prenez une place previous solution et utiliser itertools.product(*l).

Answer 2

Assez facile avec 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

Si quelqu'un est intéressé par l'algorithme, voici un moyen très simple d'utiliser la récursivité pour trouver les combos:

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

Ici, vous allez

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'] 

Si vous souhaitez réutiliser/régénérer:

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

utilisant récursion

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

ferroutage hors du JasonWoof's answer. Ce qui suit va créer une liste au lieu d'imprimer. Soyez conscient que cela peut être très lent car il nécessite beaucoup de mémoire pour stocker les valeurs.

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)] 

Résultat

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'] 

---

Ci-dessous est une substitution équivalente pour itertools.product(*iterables[, repeat]):

Cette fonction est équivalente au code suivant, sauf que la mise en œuvre effective ne construit pas résultats intermédiaires en mémoire:

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)