置换所有可能的(0,1)值数组

Question

我正在编写一个算法来生成这种数组的所有可能的排列:

n =长度
k =数组中1的数量

所以这意味着如果我们有k 1,我们将在数组中得到nk 0.

例如:n = 5; k = 3;

所以很明显这个数组有5种可能的排列,因为
n!/(k!(nk)!
5!/(3!2!)=(5*4)/ 2 = 10个
可能的数组值

以下是所有值:
11100
11010
11001
10110
10101
10011
01110
01101
01011
00111

我猜我应该使用递归算法,但我只是没有看到它.我正在用C++编写这个算法.

任何帮助,将不胜感激!

Answer 1

刚开始,00111然后std::next_permutation用来生成其余的:

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s = "00111";
    do
    {
        std::cout << s << '\n';
    }
    while (std::next_permutation(s.begin(), s.end()));
}

输出:

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

Answer 2

您可以将组合拆分为以1(n-1,k-1)开头的组合和以0(n-1,k)开头的组合.

这实际上是choose函数的递归公式.