Quelle serait une meilleure implémentation de toutes les combinaisons dans l'ordre lexicographique d'une liste déchiquetée?

Question

J'ai été mis dans une position aujourd'hui où j'avais besoin d'énumérer toutes les combinaisons possibles de la liste déchiquetée. Par exemple, une approche naïve serait:

for a in [1,2,3]: 
    for b in [4,5,6,7,8,9]: 
     for c in [1,2]: 
      yield (a,b,c) 

Ceci est fonctionnel, mais pas générale en termes de nombre de listes qui peuvent être utilisées. Voici une approche plus générale:

from numpy import zeros, array, nonzero, max 

make_subset = lambda x,y: [x[i][j] for i,j in enumerate(y)] 

def combinations(items): 
    num_items = [len(i) - 1 for i in items] 
    state = zeros(len(items), dtype=int) 
    finished = array(num_items, dtype=int) 
    yield grab_items(items, state) 
    while True: 
     if state[-1] != num_items[-1]: 
      state[-1] += 1 
      yield make_subset(items, state) 
     else: 
      incrementable = nonzero(state != finished)[0] 
      if not len(incrementable): 
       raise StopIteration 
      rightmost = max(incrementable) 
      state[rightmost] += 1 
      state[rightmost+1:] = 0 
      yield make_subset(items, state) 

Des recommandations sur une meilleure approche ou des raisons contre l'approche ci-dessus?

Answer 1

L'approche naïve peut être écrit de manière plus compacte comme une expression du générateur:

((a,b,c) for a in [1,2,3] for b in [4,5,6,7,8,9] for c in [1,2]) 

L'approche générale peut être écrit beaucoup plus en utilisant simplement une fonction récursive:

def combinations(*seqs): 
    if not seqs: return (item for item in()) 
    first, rest = seqs[0], seqs[1:] 
    if not rest: return ((item,) for item in first) 
    return ((item,) + items for item in first for items in combinations(*rest)) 

Exemple d'utilisation:

>>> for pair in combinations('abc', [1,2,3]): 
... print pair 
... 
('a', 1) 
('a', 2) 
('a', 3) 
('b', 1) 
('b', 2) 
('b', 3) 
('c', 1) 
('c', 2) 
('c', 3)