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

Question

我有一个包含 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 个元素。

Answer 1

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

解决方案是仅生成您需要的组合：在上面的示例中，使用

combinations_with_replacement(range(7), 20-7)

，它恰好生成 27132 个组合，并将元素列表附加到每个组合，以便保证每个元素至少出现一次定义。

对于您对元素进行排序的请求，

combinations_with_replacement()

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