有没有一种方法可以有效地迭代 Python 中的 'nested' 组合？

Question

我不确定如何定义我想解决的问题，但是从数字组合来看，例如：

(4, 3, 2)

我希望制作一个遍历这些数字的所有 'nested' 组合的迭代器。我的意思是它遍历：

(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (0, 1, 1), (0, 1, 2), (0, 2, 1), (0, 2, 2), ...

(1, 0, 0), (1, 1, 0), (1, 2, 0), (1, 3, 0), (1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), ...

...

(4, 0, 0), (4, 1, 0), (4, 2, 0), (4, 3, 0), (4, 1, 1), (4, 1, 2), (4, 2, 1), (4, 2, 2), ...

最好也可以在生成组合时受最大总和容量的限制（即 sum(combination) < capacity）。

我已经创建了一个生成这些组合的递归算法，但是它很慢，希望有更有效的方法。

import numpy as np 

def combinations(current, c, c_set):
    c_rec = c.copy()
    if(current == 0):
        while(c_rec[current] + 1 <= numbers[current] and c_rec[current] + 1 < capacity):
            c_rec[current] += 1
            c_set.append(c_rec.copy())

    while(c_rec[current] + 1 <= numbers[current] and c_rec[current] + 1 < capacity):
        c_rec[current] += 1
        combinations(current - 1, c_rec, c_set)
        c_set.append(c_rec)

numbers = (4,3,2)
n = len(numbers)
capacity = 7
c_init = np.zeros(n)
c_set = [c_init]            
combinations(n - 1, c_init, c_set)

Answer 1

您可以为此使用 itertools.product

from itertools import product

li = [4, 3, 2]

#Create a list of ranges
res = [range(item+1) for item in li]
#[range(0, 5), range(0, 4), range(0, 3)]

#Calculate cartesian product between elements of each list
prod = product(*res)

#Iterate over the elements
for item in prod:
    print(item)

输出将是

(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(0, 1, 0)
(0, 1, 1)
...
(1, 0, 0)
(1, 0, 1)
(1, 0, 2)
(1, 1, 0)
(1, 1, 1)
...
(2, 0, 0)
(2, 0, 1)
(2, 0, 2)
(2, 1, 0)
(2, 1, 1)
.....
(3, 0, 0)
(3, 0, 1)
(3, 0, 2)
(3, 1, 0)
(3, 1, 1)
.....

Answer 2

我可能没有完全理解你的问题，但是一个简单的嵌套 for-loop 结构不能解决你的问题吗？

for x in range(4):
    for y in range(3):
        for z in range(2):
            print((x, y, z))

Answer 3

您可以对生成器使用递归：

start = (4, 3, 2)
def groups(d):
  yield d
  for i, [a, b] in enumerate(zip(d, start)):
    if a < b:
      yield from groups(tuple([*d[:i], d[i]+1, *d[i+1:]]))

result = set(groups((0, 0, 0)))

输出：

[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (0, 3, 0), (0, 3, 1), (0, 3, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 3, 0), (1, 3, 1), (1, 3, 2), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 2, 0), (2, 2, 1), (2, 2, 2), (2, 3, 0), (2, 3, 1), (2, 3, 2), (3, 0, 0), (3, 0, 1), (3, 0, 2), (3, 1, 0), (3, 1, 1), (3, 1, 2), (3, 2, 0), (3, 2, 1), (3, 2, 2), (3, 3, 0), (3, 3, 1), (3, 3, 2), (4, 0, 0), (4, 0, 1), (4, 0, 2), (4, 1, 0), (4, 1, 1), (4, 1, 2), (4, 2, 0), (4, 2, 1), (4, 2, 2), (4, 3, 0), (4, 3, 1), (4, 3, 2)]

有没有一种方法可以有效地迭代 Python 中的 'nested' 组合？

Is there a way to efficiently iterate over 'nested' combinations in Python?

python

combinatorics

itertools