04.C++算法竞赛——排列和组合问题以及子集生成问题

柆

我也是学生，也在学习算法竞赛，可能还不如各位大佬强，如有错误或遗漏请及时告知我哦，以方便我改正，相互学习也相互进步。有语义表达不畅的情况，也可以及时提醒我哦。
本篇文章参考了《算法竞赛入门到进阶》—罗勇军、郭卫斌的内容，衷心感谢它的作者，这本书也是算法竞赛入门最佳之作。
本文所有代码均经过编译通过。
电脑观看，效果最佳。
<hr/>排列问题

排列一般是从n个数中选取m个数进行排列( m\leq n )，共有 \frac{n!}{(n−m)!} 种排列。 m=n 时是排列问题的特殊变化，它被称为全排列，共有 n！个。不同顺序的相同数，组成的数列在排列中是不同的。
如有三个数1、2、3，选取两个数进行排列，则有 \frac{n!}{(n−m)!}=\frac{3!}{(3-2)!}=3!=6 种，即：12、13、23、21、31、32。
现有问题如下：输入这n个数，输出这n个数的全排列。
解法一：

先来了解一些基础知识（会的可以跳过）：
<hr/>sort，是STL中用来排序的算法，时间复杂度 O(n\log n) ，无返回值，它的头文件是algorithm。它有两种可选形式：
1.sort(first,last)。first和last是两个相同类型的指针，first指向第一个元素，last指向末尾元素的后一位。注意：first和last指针的类型必须有比较函数且它排序的范围是[first,last)。即包括first而不包括last。
例如：int a[5]={1,4,2,5,3};sort(a,a+5);a是指向a[0]的指针，a+5则指向a[5]的指针，这是数组末尾的后一位。这样才能把整个数组排序。
2.sort(first,last,cmp)。同时我们还可以自定义比较函数cmp(当是自定义类型或想要指定从小到大还是从大到小时)，详情看：sort自定义排序。
<hr/>next_permutation(first,last)，是STL用来求下一个排列的算法，时间复杂度 O(n) 。如果没有下一个排列了，则返回0，反之返回1。它的头文件是algorithm。排列结束后，它会把排列好的结果，放进原数组中。这个函数好的一点是：它能通过这个字符序列，求出下一个字典序排列，它是有顺序的。注意：它求下一个排列的范围是[first,last)。即包括first而不包括last。它有一个类似的函数prev_permutation(first,last)，它用来求前一个排列。
<hr/>现在我们便可以用STL实现这个算法了，STL大法好（雾）。
首先，将原数组排序，使原数组按从小到大的顺序排列，变为最小序列，这样我们就不会漏掉一些解。
然后用do-while进行循环，因为如果用while，会先执行next_permutation，使数组装的是下一个排列，这样就会漏掉第一个解。于是我们先输出一遍，再调用next_permutation。`
代码如下：
#include<algorithm>
#include<iostream>
using namespace std;
void permutations(int a[],int n){//a是数组名，n是数组元素个数
    sort(a,a+n);
    do{
        for(int i=0;i<n;i++){
            cout<<a;
        }
        cout<<endl;
    }while(next_permutation(a,a+n));
    return;
}
解法二：

那么，我们能不能自己实现这个算法呢，当然可以。我们可以用递归解决这个问题。
假设我们要进行全排列的数列为1，7，9。让我们把第一位和全部这三位进行依次交换，得：
1，7，9       7，1，9       9，7，1
随后把这3组数按照相同的方式进行排列，不过保持第一位不动，用第二位与剩下的2位进行交换。
第一组：1，7，9       1，9，7
第二组：7，1，9       7，9，1
第三组：9，7，1       9，1，7
现在交换到第3位时，有且仅有自己可以被交换，但交换完还是自己本身没有意义。此时生成的 n!=6 个数列就是这3个数的全排列。
总的来说，这样的操作就像把这个数列中的所有数(3个)都依次放在第一位，此时有3种情况，接着这3种情况分别把剩下的2个数字依次放进第二位，此时有 n(n-1)=3*2=6 种情况。相同的，放到第3位时，此时仅有一个数字，只有一种选择。于是我们就得到了 n! 个排列。可能有些难理解，请仔细体会。
代码如下：
#include<iostream>
using namespace std;
void permutations(int a[],int beg,int end){//这里是[beg,end]
    if(beg==end){//已无数可交换，打印，相当于交换到第n位时
        for(int i=0;i<=end;i++){
            cout<<a;
        }
        cout<<endl;
        return;
    }
    for(int i=beg;i<=end;i++){//把自己和剩下的位进行交换，保持前面的位不动
        swap(a[beg],a);//交换
        permutations(a,beg+1,end);//保持这一位不动，开始用下一位对剩下的数交换
        swap(a[beg],a);//还原，为下一次交换做准备
    }
    return;
}
这两种方法时间复杂度都是 O(n!) 。可能会有人说，这时间复杂度太高了，有没有效率比这更高的算法呢？没有，因为全排列就有 n! 个，不存在有一种算法时间复杂度低于 O(n!) 。
现加强问题为：输入这n个数，在n个数中选取3个数的排列，并打印。
其实只需把解法二中的：if(beg==end) 换为if(beg==3) ，且把if下的语句换成cout<<a[0]<<a[1]<<a[2]<<endl; 即可。参照上文，这次我们不把它放到第n位，而是依次放到第3位时就停止，此时有 n(n-1)(n-2) 种排列，然后输出。
子集生成问题

假设有一个集合{ {a_1,a_2,...,a_n} }，那么它的子集是{ \oslash },{ a_1 },{ a_2 },{ a_3 },{ a_1,a_2 },{ a_1,a_2,a_3 }...共 2^n 个。
现提出问题：输入数字n代表集合的元素个数，输出这个集合的每个子集的a的下标(指的是 a_1 中的下标1)，空集用empty来表示，每个子集占一行。
二进制解决方法

为了方便观察，假设有一个有三个元素的集合{ a_0,a_1,a_2 }，它的子集是：{ \oslash },{ a_0 },{ a_1 },{ a_1,a_0 },{ a_2 },{ a_2,a_0 },{ a_2,a_1 },{ a_2,a_1,a_0 }。
假设我们把二进制最右端的下标规定为0，且向左一位就增大1。
它们与二进制与十进制的关系如下（抱歉，知乎表格里不能插入公式，小标以_来表示）：

子集	{empty}	{a_0}	{a_1}	{a_1,a_0}	{a_2}	{a_2,a_0}	{a_2,a_1}	{a_2,a_1,a_0}
二进制	000	001	010	011	100	101	110	111
十进制	0	1	2	3	4	5	6	7

观察可得：子集中每个元素的下标所对应的二进制位置都为1，其余位置为0。(如{ a_2,a_0 }，二进制中下标为2和0的地方是1，也就是101)且十进制中数依次递增1。且二进制的最大位数恰好是集合的元素数量。
代码如下：
#include<iostream>
using namespace std;
void subset(int n){//n为集合的元素个数
    cout<<"empty"<<endl;
    for(int i=1;i<(1<<n);i++){//这里跳过0，是因为0代表空集。i<(1<<n)是因为与i<=(1<<n-1)等同
        for(int j=0;j<n;j++){//判断每一位有没有1
            if((i>>j)&1){//判断i的二进制中第j位有没有1
                cout<<j<<" ";
            }
        }
        cout<<endl;
    }
    return;
}
组合问题

组合一般是从n个数中选取m个数( m\leq n )，共有  \frac{n!}{m!(n-m)!} 种组合。注意：排列需要考虑元素的放置顺序，而组合则不考虑。
如有三个数1、2、3，选取两个数进行组合，则有 \frac{n!}{m!(n-m)!}=\frac{3!}{2!(3-2)!}=3 种。即：1,2、1,3、2,3。
现有问题如下：输入这n,m，输出从n个数选取m个数的组合。
next_permutation只适用于排列，并不适用于组合。因此我们需要自己实现算法。
联想到上文的子集生成问题，同样地，子集也不考虑元素放置位置。但是，子集的元素数量不一定是相同的，但组合问题我们却需要规定每次组合数量为m。因此，i每自增1，就判断i的二进制中1的个数是否为m，如果是就输出。但是，如何判断二进制串中1的个数呢？
1.遍历二进制串，此算法时间复杂度为 O(n) ，n为二进制串中1和0的总数量。
2.还有一种神奇的方法：n&(n-1)，它每次可以消去二进制串中的一个1。它的时间复杂度是 O(k) ，显然 k\leq n 。
代码如下：
#include<iostream>
using namespace std;
int count(int num){//返回sum中1的个数
    int sum=0;
    while(num){
        sum++;
        num&=num-1;
    }
    return sum;
}
void c(int arr[],int n,int m){//arr为储存n个数的数组，n为元素数量，m为选取个数
    for(int i=1;i<(1<<n);i++){
        if(count(i)==m){//1的个数为m，输出
            for(int j=0;j<n;j++){
                if((i>>j)&1){//看哪一位是1
                    cout<<arr[j]<<" ";
                }
            }
            cout<<endl;
        }
    }
}

睾端丸家

排版的很累，请支持一下吧。