python - 可替换多个可迭代对象或与订单无关的产品的高效组合

Question

我正试图在 Python 中找到一个像这样工作的高性能解决方案:

>>> func([1,2,3], [1,2])
[(1,1), (1,2), (1,3), (2,2), (2,3)]

这类似于 itertools.combinations_with_replacement，除了它可以接受多个迭代。它也类似于 itertools.product，只是它省略了与顺序无关的重复结果。

所有输入都将是同一系列的前缀(即它们都以相同的元素开头并遵循相同的模式，但可能具有不同的长度)。

该函数必须能够将任意数量的可迭代对象作为输入。

给定一组列表 A、B、C，...，这是生成这些结果的算法的草图.

assert len(A) <= len(B) <= len(C) <= ...
for i in 0..len(A)
  for j in i..len(B)
    for k in j..len(C)
        .
        .
        .
      yield A[i], B[j], C[k], ...

我不能做的事

• 使用 itertools.product 并过滤结果。这必须是高性能的。
• 使用递归。函数开销会使它比使用 itertools.product 和过滤合理数量的可迭代对象慢。

我怀疑有一种方法可以用 itertools 来做到这一点，但我不知道它是什么。

编辑:我正在寻找花费最少时间的解决方案。

编辑 2: 我试图优化的内容似乎有些困惑。我将举例说明。

>>> len(list(itertools.product( *[range(8)] * 5 )))
32768
>>> len(list(itertools.combinations_with_replacement(range(8), 5)))
792

第一行给出了掷 5 个 8 面骰子的order-dependent 可能性的数量。第二个给出了order-independent 可能性的数量。无论 itertools.product 的性能如何，与 itertools.combinations_with_replacement 相比，它需要 2 个数量级 的迭代次数才能获得结果。我正在尝试找到一种方法来执行类似于 itertools.combinations_with_replacement 的操作，但使用多个迭代器可以最大限度地减少迭代次数或时间性能。 (product 在 中运行，而 combinations_with_replacement 在 中运行，其中 M 是骰子的面数，N 是骰子的数量)

Answer 1

此解决方案没有递归或过滤。它试图仅生成索引的升序序列，因此它仅可用于同一集合的前缀。此外，它仅使用索引来标识元素，因此它不会强制系列元素具有可比性甚至可哈希。

def prefixCombinations(coll,prefixes):
    "produces combinations of elements of the same collection prefixes"
    prefixes = sorted(prefixes) # does not impact result through it's unordered combinations
    n = len(prefixes)
    indices = [0]*n
    while True:            
        yield tuple(coll[indices[i]] for i in range(n))
        #searching backwards for non-maximum index
        for i in range(n-1,-1,-1):
            if indices[i] < prefixes[i] - 1 : break
        # if all indices hits maximum - leave
        else: break
        level = indices[i] + 1
        for i in range(i,n): indices[i] = level

例子是

>>> list(prefixCombinations([1,2,3,4,5], (3,2)))
[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3]]

>>> list(prefixCombinations([1,2,3,4,5], (3,2,5)))
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 5], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 3], [1, 3, 4], [1, 3, 5], [2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 2, 5], [2, 3, 3], [2, 3, 4], [2, 3, 5]]

>>> from itertools import combinations_with_replacement
>>> tuple(prefixCombinations(range(10),[10]*4)) == tuple(combinations_with_replacement(range(10),4))
True