algorithm - 迭代每个 k 子集，使得每个元素在迭代过程中被同等频繁地选择

Question

假设我们有一个包含 n 个元素的集合。我想有效地迭代具有 k 元素的所有子集，这样在迭代过程中，元素的选择大致相同。

---

示例

我们有 7 个元素:[a,b,c,d,e,f,g] 并且我们想要所有 4 个子集。总共有 binom(7)(4) 子集。

1. 迭代:[a,b,c,d]
2. 迭代:[e,f,g,a](现在每个元素至少被选择一次)
3. 迭代:[b,c,d,e]
4. 迭代:[f,g,a,b](现在每个元素至少被选择两次)
5. 迭代:...

只有当n是素数时，这才有效。它不适用于 n = 6 和 k = 3。

---

我需要一种算法来获取所有可能的子集，而无需事先生成它们(对于 binom(30)(15)，我们已经拥有超过 1.5 亿个子集)。

(我想用javascript实现这个，但欢迎任何建议。)

Answer 1

如果 n = 2k，那么有一个简单的解决方案。枚举所有包含 1 的 k 子集，每个子​​集后跟其补集。

如果 n ≠ 2k 但 k 除以 n，那么我认为您需要 construction底层Baranyai's theorem使所有数字彼此出现一次。这不是一个理想的解决方案，因为它既需要复杂的算法，又需要将整个列表立即保存在内存中。

我不知道如何立即处理其他情况(尽管由于问题的对称性，NP 硬度降低(例如，给定 n 、 k 和 g ，确定是否可以保持最大至多 g) 的差异似乎极不可能出现)。也许您可以描述您的后备需求。