如何在Python 2.5中编写类似itertools.product的函数

Question

我有一个包含多个元组的列表，比如：

A=[(1,2,3), (3,5,7,9), (7)] 

我想从每个元组中选一个元素，生成所有可能的组合。

1,3,7
1,5,7
1,7,7
...
3,9,7

我可以有任意数量的元组，而且每个元组里面可以有任意数量的元素。不过，我不能使用 itertools.product()，因为我用的是 Python 2.5。

Answer 1

在玩生成器的时候，我也找到了一个版本的 itertools.product，这个版本几乎和官方库的速度一样快，而且完全兼容，不会生成中间结果：

def product(*args, **kwds):
    "Alternative fast implementation of product for python < 2.6"
    def cycle(values, uplevel):
        for prefix in uplevel:       # cycle through all upper levels
            for current in values:   # restart iteration of current level
                yield prefix + (current,)

    stack = (),             
    for level in tuple(map(tuple, args)) * kwds.get('repeat', 1):
        stack = cycle(level, stack)  # build stack of iterators
    return stack

在使用 Python 2.7.3 的时候，我发现这个版本的性能真的很好（通常只慢5到10倍，而且内存使用基本相同）。

>>> import itertools as itt
>>> timeit for _ in itt.product(range(20), range(3), range(150)): pass
1000 loops, best of 3: 221 µs per loop
>>> timeit for _ in product(range(20), range(3), range(150)): pass
1000 loops, best of 3: 1.14 ms per loop

编辑：把代码做得更简单，并且适配了 Python 3。

Answer 2

def product(*iterables):
    """ Equivalent of itertools.product for versions < 2.6,
        which does NOT build intermediate results.
        Omitted 'repeat' option.
        product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    """
    nIters = len(iterables)
    lstLenths = []
    lstRemaining = [1]
    for i in xrange(nIters-1,-1,-1):
        m = len(iterables[i])
        lstLenths.insert(0, m)
        lstRemaining.insert(0, m * lstRemaining[0])
    nProducts = lstRemaining.pop(0)

    for p in xrange(nProducts):
        lstVals = []

        for i in xrange(nIters):
            j = p/lstRemaining[i]%lstLenths[i]
            lstVals.append(iterables[i][j])
        yield tuple(lstVals)

当然可以！请把你想要翻译的内容发给我，我会帮你把它变得更简单易懂。

Answer 3

在itertools.product的文档中，有一个关于如何在Python 2.5中实现它的例子：

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    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)