itertools combations with replacement with limitations

Question

有没有更好的方法来列出所有可能的组合，并用每个元素的最小和最大出现次数进行替换，而不是 (1) 列出没有这些限制的所有可能组合 itertools.combinations_with_replacement() 然后(2)一一检查结果是否符合限制条件？

举个例子，假设我有一个数组 [a b c]，我想从中提取 10 次，但我想查看每个元素至少 1 次但不超过一半次（即5次），我不想看到下面的

b b b b b c c c c c # no a
a a a a a a b b c c # a more than 5 times

我的实际数组更大，有 20 个元素可以从中绘制 100 次...

提前致谢

编辑：

这是我尝试过的方法，但显然我的 20 个元素被绘制了 100 次似乎效率不高...

a = []
for c in list(itertools.combinations_with_replacement(range(4), 10)):
    valid = 1
    for i in range(4):
        if not c.count(i) or c.count(i) > 5:
            valid = 0
            break
    if valid:
        a.append(c)

我真正想做的是我有 20 个项目，我想计算出我可以从中生成的所有可能的篮子，比例为增量整数（即 1%、2% 等） , 没有 1.5%)，因此 100 次加起来就是 100%。每个项目都应始终出现，但其中 none 应超过 50%...

Answer 1

这是我根据您发布的方法提出的建议：

至少查看所有元素一次：您可以从填充一组元素的结果数组开始。

从这样的 "seed" 开始，在一定程度上限制了要检查和消除重复项的组合的数量；它还简化了检查。

import itertools
a = []
seed = (0,1,2,3)
for c in itertools.combinations_with_replacement(range(4), 6):
    valid = True
    for i in range(4):
        if c.count(i) > 4:
            valid = False
            break
    if valid:
        a.append(c+seed)
a

可以创建一个生成器表达式（同理）：

import itertools
from collections import Counter
a = ((0,1,2,3) + c for c in itertools.combinations_with_replacement(range(4), 6) if max(Counter(c).values()) < 5)

Answer 2

您对实际需求的描述提出了一个直接、高效且简单（尽管不够优雅）的解决方案。

首先假设您没有少于 50 的要求：

只需使用 19 个嵌套的 for 循环。外面的循环从 1 到 81，下一个循环从 1 到 82 减去第一个，依此类推。然后最后一个数字补到 100。

要添加小于 50% 的要求，您需要使循环在 50 处停止（如果它小于上面计算的数字）。如果最终数字大于 50，他们还需要从更高的起点开始。

这将非常高效和直接 - 它将只生成您想要的那些。它可以被重写为使用可变数字而不是固定的 20，尽管这使得它相当复杂。

不过，user2357112 的观点很好，用这个简单的公式强调了。粗略估计这里的组合数量明显大于2e13。这种蛮力方法不太可能奏效。您可能需要更复杂的方法来解决根本问题。

itertools combations with replacement with limitations

itertools cominbations with replacement with limitations

python

itertools