代码之家 › 专栏 › 技术社区 › Pedro Queirós

无中间结果的Itertools产品

itertools product python

Pedro Queirós · 技术社区 · 7 年前

给定一个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。产品(list,repeat=k-length)将非常有效,但我不允许使用它。我看过源代码,虽然它对小序列很有效,但对于长序列,使用了太多内存。非常正常,因为我们正在创建len(list)**k长度组合。我的问题是,是否可以创建一个不创建中间“结果”列表的iterable生成器? 我一直在摆弄这个函数,并在考虑递归解决方案,但找不到任何解决问题的方法。

参考代码:

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“for循环”。

如果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个结果

1 回复 | 直到 7 年前

hansaplast 7 年前

有了这些新信息,我将完全重写我的帖子。如果需要选取长度的元组 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 可能就是你想要的。它生成从内部调用到外部调用的所有值
我使用元组是因为通常列表是可变的,您通常不希望任何内部/外部调用与其他列表发生冲突。虽然列表在这里也可以工作,但不可变性generall在递归中表现得更好

更新:无递归

如果出于任何原因,您希望不使用递归(例如,如果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)