迭代每个 k 子集，使得每个元素在迭代过程中被同样频繁地选择
Iterate over each k-subset such that each element is equally often selected during iteration
假设我们有一个包含 n 个元素的集合。我想用 k 元素有效地迭代所有子集，这样在迭代过程中，元素的选择大致相等。
例子
我们有 7 个元素：[a,b,c,d,e,f,g] 并且我们想要所有 4 个子集。总共有 binom(7)(4) 个子集。
- 迭代：
[a,b,c,d]
- 迭代：
[e,f,g,a]（现在每个元素至少被选中一次）
- 迭代：
[b,c,d,e]
- 迭代：
[f,g,a,b]（现在每个元素至少被选中两次）
- 迭代：
...
这只适用于 n 是质数的情况。它不适用于 n = 6 和 k = 3。
我需要一种算法来获取所有可能的子集而不事先生成它们（对于 binom(30)(15) 我们已经有超过 1.5 亿个子集）。
（我想用 javascript 实现这个，但欢迎任何建议。）
如果 n = 2k，那么有一个简单的解决方案。枚举所有包含 1 的 k 个子集，每个子集后面跟着它的补码。
如果 n ≠ 2k 但 k 整除 n，那么我认为您需要 construction underlying Baranyai's theorem 来保持所有数字彼此出现一次。这不是一个理想的解决方案，因为它既需要复杂的算法，又需要将整个列表立即保存在内存中。
我不知道如何处理其他情况（尽管由于问题的对称性，NP 硬度降低（例如，给定 n 和 k 和 g，确定是否可以保留至多 g) 的最大差异似乎极不可能出现）。也许您可以描述您的后备要求。
这个答案很有效，但不够精确。
存在一种对组合进行排序的有效算法，即给定 n 和 k 以及一个整数 j ∈ {0, ..., (n choose k) − 1}，return 中的第 j 个组合字典顺序。
将该算法与随机排列 {0, ..., (n choose k) − 1} 的格式保留加密方案组合在一起，您将得到一个近似平衡每个元素频率的算法。我想我会使用 AES 的 FFX 模式来获得 {0, ..., m−1} 的排列，其中 m 是两个的最小幂，不小于 n 选择 k 然后骑自行车，但是有人比我更了解加密货币的人可能有更好的主意。
为了控制方差，我将此算法概括为保留一个包含固定数量组合的池，然后交替地 (1) 贪婪地从池中取出最不公平的组合 (2) 添加下一个组合到游泳池。
假设我们有一个包含 n 个元素的集合。我想用 k 元素有效地迭代所有子集，这样在迭代过程中，元素的选择大致相等。
例子
我们有 7 个元素：[a,b,c,d,e,f,g] 并且我们想要所有 4 个子集。总共有 binom(7)(4) 个子集。
- 迭代：
[a,b,c,d] - 迭代：
[e,f,g,a]（现在每个元素至少被选中一次） - 迭代：
[b,c,d,e] - 迭代：
[f,g,a,b]（现在每个元素至少被选中两次） - 迭代：
...
这只适用于 n 是质数的情况。它不适用于 n = 6 和 k = 3。
我需要一种算法来获取所有可能的子集而不事先生成它们（对于 binom(30)(15) 我们已经有超过 1.5 亿个子集）。
（我想用 javascript 实现这个，但欢迎任何建议。）
如果 n = 2k，那么有一个简单的解决方案。枚举所有包含 1 的 k 个子集，每个子集后面跟着它的补码。
如果 n ≠ 2k 但 k 整除 n，那么我认为您需要 construction underlying Baranyai's theorem 来保持所有数字彼此出现一次。这不是一个理想的解决方案，因为它既需要复杂的算法，又需要将整个列表立即保存在内存中。
我不知道如何处理其他情况（尽管由于问题的对称性，NP 硬度降低（例如，给定 n 和 k 和 g，确定是否可以保留至多 g) 的最大差异似乎极不可能出现）。也许您可以描述您的后备要求。
这个答案很有效，但不够精确。
存在一种对组合进行排序的有效算法，即给定 n 和 k 以及一个整数 j ∈ {0, ..., (n choose k) − 1}，return 中的第 j 个组合字典顺序。
将该算法与随机排列 {0, ..., (n choose k) − 1} 的格式保留加密方案组合在一起，您将得到一个近似平衡每个元素频率的算法。我想我会使用 AES 的 FFX 模式来获得 {0, ..., m−1} 的排列，其中 m 是两个的最小幂，不小于 n 选择 k 然后骑自行车，但是有人比我更了解加密货币的人可能有更好的主意。
为了控制方差，我将此算法概括为保留一个包含固定数量组合的池，然后交替地 (1) 贪婪地从池中取出最不公平的组合 (2) 添加下一个组合到游泳池。