具有特定值重复次数的第 K 个排列
Kth permutation with specific number of value repetition
我正在寻找一种算法，它将 return 包含特定数量的真值和假值的 bool 向量的第 k 个排列。并且在不生成所有先前排列的情况下这样做，例如使用 c++ next_permutation(...)。
例如我有 00011 并且想要第 5 个字典顺序排列 (01010)。
有什么办法吗？
包含 2x true 和 3x false 的完整排列列表：
- 00011
- 00101
- 00110
- 01001
- 01010
- 01100
- 10001
- 10010
- 10100
- 11000
我在谷歌上搜索了很多不同的生成排列的算法，但是 none 对于具有特定数量的重复元素的第 k 个排列。
感谢您的任何建议:)
如果您有二项式系数的来源，一次生成一个位很容易。 （由于涉及的数字很小——我们知道 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 时，我们就完成了。 （在必要时通过对位掩码进行或运算来构建 return 值的实际实现可以在 n1 达到 0 时停止，从而节省了几个步骤。）
我正在寻找一种算法，它将 return 包含特定数量的真值和假值的 bool 向量的第 k 个排列。并且在不生成所有先前排列的情况下这样做，例如使用 c++ next_permutation(...)。 例如我有 00011 并且想要第 5 个字典顺序排列 (01010)。
有什么办法吗？
包含 2x true 和 3x false 的完整排列列表：
- 00011
- 00101
- 00110
- 01001
- 01010
- 01100
- 10001
- 10010
- 10100
- 11000
我在谷歌上搜索了很多不同的生成排列的算法，但是 none 对于具有特定数量的重复元素的第 k 个排列。
感谢您的任何建议:)
如果您有二项式系数的来源，一次生成一个位很容易。 （由于涉及的数字很小——我们知道 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 时，我们就完成了。 （在必要时通过对位掩码进行或运算来构建 return 值的实际实现可以在 n1 达到 0 时停止，从而节省了几个步骤。）