我正在寻找一种算法，该算法将返回包含特定数量的真值和假值的 boolean vector 的 kth 排列。并且这样做不会像使用 c++ next_permutation(...) 那样生成所有先前的排列。 例如，我有 00011，想要第五个字典排列 (01010)。
有没有办法做到这一点？
包含 2x true 和 3x false 的排列的完整列表:
- 00011
- 00101
- 00110
- 01001
- 01010
- 01100
- 10001
- 10010
- 10100
- 11000
我在 google 上搜索了很多不同的算法来生成排列，但没有搜索到具有特定数量的重复元素的 kth 排列。
感谢您的建议:)
最佳答案
如果您有二项式系数源，那么一次生成一个位是很容易的。 (由于涉及的数字很小——我们知道k适合无符号整数类型——可以预先计算可能的二项式系数。)
现在，考虑我们需要生成 n0 个零和 n1 个的情况。可能的有效位序列的数量为 (n0+n1)Cn1(其中 nCk 是二项式系数)，因为有 n0 + n1可以放置n1一位的位置。其中，(n0+n1-1)Cn1 以 0 开头，其余 (n0+n1-1)C(n1-1) 以 1 开头.因此，如果k大于或等于(n0+n1-1)Cn1，我们输出1，递减n1 ，并将k递减(n0+n1-1)Cn1；否则，我们输出 0 并递减 n0。
当n0和n1都达到0时，我们就完成了。 (在必要时通过或运算位掩码来构建返回值的实际实现可以在 n1 达到 0 时停止，从而节省了一些步骤。)
关于c++ - 具有特定值重复次数的第 K 次排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42742214/