python - 什么会更好地实现锯齿列表的字典顺序的所有组合？

Question

今天我被安排在一个职位上，需要枚举锯齿状列表的所有可能组合。例如，一个天真的方法是:

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

这是功能性的，但就可使用的列表数量而言并不通用。这是一个更通用的方法:

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)

关于更好的方法的任何建议或反对上述方法的理由？

Answer 1

朴素的方法可以更简洁地写成生成器表达式:

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

可以使用递归函数更简单地编写一般方法:

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

示例用法:

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