如何生成至少包含每个元素一次的 k 个元素的所有长度 n 组合（带替换）？

How to generate all length n combinations of k elements (with replacement) that contain each element at least once?

提问人：kevinsmith 提问时间：10/27/2023 最后编辑：kevinsmith 更新时间：10/27/2023 访问量：41

问：

我有一个包含 7 个元素的列表，我将用这些元素填充另一个长度为 50 的列表。我想生成一个数据帧，其中每行代表将这 7 个元素选择到 50 个插槽中的一种可能方法。但是，我只对至少包含 7 个元素中每个元素一次的排列感兴趣。

这是我目前拥有的方法，但希望就如何更有效地编写此内容以节省时间提出任何建议（运行需要很长时间）。

from math import comb
import numpy as np
import pandas as pd
import itertools

elements = [1,2,3,4,5,6,7]

combos = pd.DataFrame(itertools.combinations_with_replacement(range(7),50))

keep_rows = combos.apply(lambda row: np.sum([a in list(row) for a in elements])==7,axis=1)

有没有更快的方法来实现这一目标？

编辑此外，我只需要按升序排列（因此使用 itertools.combinations_with_replacement（））。例如，[1,2,3,4,5,6,7,...,7]感兴趣，但[7,1,2,3,4,5,6,...,7]不感兴趣。

编辑 2列表错误地有 8 个元素。

Python 性能 组合 排列 内存高效

评论

0赞 Woodford 10/27/2023
你不希望所有组合都可能，对吧？大约有 7^50 个不同的行。
0赞 kevinsmith 10/27/2023
是的，我只想要所有 7 个元素都存在的组合。基于运行一次上述代码，我认为它应该在 1300 万行左右。另外（我也会把这个添加到问题中），我确实关心排序顺序 - 所以 [0,1,2,3,4,5,6,7,7,7,7,...,7] 感兴趣，但 [7,0,1,2,3,4,5,6,...,7] 不是。
0赞 Tim Roberts 10/27/2023
不，它的方式，远不止于此。从 .现在有 8^42 种方法可以完成符合您条件的序列，这是一个 38 位数字的数字。你一直说 7，但你的列表有 8 个元素。[0,1,2,3,4,5,6,7]
0赞 kevinsmith 10/27/2023
我只对升序排列感兴趣，所以从开始只留下一种完成的可能性，即 .感谢您发现我编辑了这篇文章，因此列表有 7 个元素。[1,2,3,4,5,6,7][1,2,3,4,5,6,7,7,...,7]

答：

1赞 gimix 10/27/2023 #1

你的方法的问题在于你生成了很多无用的组合。我没有对你原来的 50 个插槽进行数学计算或计算;但是让我们考虑一个更简单的情况，在 20 个插槽中有 7 个元素：您将生成 230230 个连击，然后丢弃其中的大部分并仅保留 27132 个 - 当然，当插槽数量增加时，丢弃的连击数量也会增加。

解决方案是只生成您需要的组合：在上面的示例中，使用 ，它正好产生 27132 个组合，并在每个组合后附加元素列表，以便根据定义保证每个元素至少出现一次。combinations_with_replacement(range(7), 20-7)

重新请求对元素进行排序，按字典顺序输出其结果，因此这不是问题。但是，使用我的解决方案，一旦将元素列表附加到每个组合中，您将需要对每个组合进行排序。这会减慢速度，但它仍然应该比仅仅为了丢弃它们而创建大量无用的结果要快得多。combinations_with_replacement()

评论

0赞 kevinsmith 10/27/2023
谢谢，这正是我要找的！

上一个：如何在 R 中排列几对变量之间的相关性？

下一个：python 中 m 个元素的 n 个列表的随机抽样