不包括项目的高效笛卡尔积

Question

我试图让 11 个值的所有可能组合重复 80 次，但过滤掉总和大于 1 的情况。下面的代码实现了我正在尝试做的事情，但需要几天时间运行:

import numpy as np
import itertools

unique_values = np.linspace(0.0, 1.0, 11)

lst = []
for p in itertools.product(unique_values , repeat=80):
    if sum(p)<=1:
        lst.append(p)

上面的解决方案可行，但需要太多时间。此外，在这种情况下，我必须定期将 'lst' 保存到磁盘中并释放内存以避免任何内存错误。后半部分很好，但是代码需要几天（或者可能几周）才能完成。

还有其他选择吗？

Answer 1

OP 只需要 10 的分区，但这是我同时编写的一些通用代码。

def find_combinations(values, max_total, repeat):
    if not (repeat and max_total > 0):
        yield ()
        return
    for v in values:
        if v <= max_total:
            for sub_comb in find_combinations(values, max_total - v, repeat - 1):
                yield (v,) + sub_comb


def main():
    all_combinations = find_combinations(range(1, 11), 10, 80)
    unique_combinations = {
        tuple(sorted(t))
        for t in all_combinations
    }
    for comb in sorted(unique_combinations):
        print(comb)

main()

Answer 2

好的，这样会更高效一些，你可以像这样使用生成器，并根据需要取值：

def get_solution(uniques, length, constraint):
    if length == 1:
        for u in uniques[uniques <= constraint + 1e-8]:
            yield u
    else:
        for u in uniques[uniques <= constraint + 1e-8]:
            for s in get_solution(uniques, length - 1, constraint - u):
                yield np.hstack((u, s))

g = get_solution(unique_values, 4, 1)
for _ in range(5):
    print(next(g))

打印

[0. 0. 0. 0.]
[0.  0.  0.  0.1]
[0.  0.  0.  0.2]
[0.  0.  0.  0.3]
[0.  0.  0.  0.4]

与你的功能比较：

def get_solution_product(uniques, length, constraint):
    return np.array([p for p in product(uniques, repeat=length) if np.sum(p) <= constraint + 1e-8])

%timeit np.vstack(list(get_solution(unique_values, 5, 1)))
346 ms ± 29.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit get_solution_product(unique_values, 5, 1)
2.94 s ± 256 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

不包括项目的高效笛卡尔积

Efficient cartesian product excluding items

python

cartesian-product

itertools