Itertools产品没有中间结果

Question

给定一个X元素列表，我需要生成一个k长度的序列。如果list = [1,2,3]且k = 2，结果将是：

 ('1', '1')
 ('1', '2')
 ('1', '3')
 ('2', '1')
 ('2', '2')
 ('2', '3')
 ('3', '1')
 ('3', '2')
 ('3', '3')

itertools.product（list，repeat = k-length）可以很好地工作，但我不允许使用它。我已经看过源代码，虽然它对小序列很有效，但对于较长的序列，使用了太多的内存。很正常，因为我们正在创建len（list）** k长度组合。我的问题是，是否有可能创建一个不会创建中间“结果”列表的可迭代生成器？我一直在摆弄这个函数并考虑一个递归的解决方案，但却找不到解决我问题的任何东西。

代码：

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)

另一种方法：

def possible_combinations(sequence):
    for a in sequence:
        for b in sequence:
            yield(a,b)

for combo in possible_combinations('123'):
    print(combo)

使用此代码，我将得到3 ** 2 = 9个结果，其中3是'123'字符串的长度，2是k。如果k等于2，这种方法也会起作用，但是假设k动态变化，我需要k'for循环'，而不仅仅是2'循环'。

如果k = 3：

def possible_combinations(sequence):
    for a in sequence:
        for b in sequence:
            for c in sequence:
                 yield(a,b,c)

for combo in possible_combinations('123'):
    print(combo)

现在我有3 ** k = 27的结果。如果k为4，则需要添加另一个for循环，如下所示：

def possible_combinations(sequence):
    for a in sequence:
        for b in sequence:
            for c in sequence:
                 for d in sequence:
                     yield(a,b,c,d)

for combo in possible_combinations('123'):
    print(combo)

现在我有3 ** 4 = 81的结果

Answer 1

有了新信息，我将完全重写我的帖子。如果你需要从序列k中选择长度为seq的元组，那么最简单的解决方案就是使用递归：

def k_sequence(seq, k, chosen = ()):
    if k == 0:
        yield chosen
    else:
        for i in seq:
            yield from k_sequence(seq, k-1, chosen + (i,))

for combo in k_sequence([1,2,3], 3):
    print(combo)

一些解释：

• yield from是你可能正在寻找的。它产生从内部调用到外部调用的所有值
• 我使用元组，因为通常列表是可变的，你通常不希望任何内部/外部调用与其他人的列表混淆。虽然列表也在这里工作，但不变性通用在递归方面更好

更新：没有递归

如果因为任何原因你想要没有递归（例如，如果k非常大，你会遇到递归或内存限制），你可以做这样的事情：让我们说seq=[1,2,3] k=3你可以想象你有三个指针都指向到第一个，列表中的1，然后你将第一个指针向下移动直到你到达结尾，然后你将指针返回到零并将第二个指针移动到下一个元素，依此类推。

def k_sequence(seq, k):
    pointers = [0] * k
    while True:
        yield tuple(seq[i] for i in pointers)
        p = 0
        pointers[p] += 1
        while pointers[p] == len(seq):
            pointers[p] = 0
            p += 1
            if p == len(seq):
                return
            pointers[p] += 1

for combo in k_sequence([1,2,3], 3):
    print(combo)