1.枚举int值，统计二进制bit中1的个数
1.1记忆化统计1的个数，x^(x-1)直接统计
//enum int comb
int count(unsigned int x){
int i = 0;
while(x != 0){
x = x&(x-1);
i++;
}
return i;
}
void enumComb(int N,int M){
int one[1<<15];
for(int i = 0 ; i < (1 << (N+1)/2) ; i++){
one[i] = count(i);
}
int half = N/2;
for(int i = 1 ; i < (1 << half) ; i++){
for(int j = 1 ; j < (1 << N-half) ; j++){
if(one[i] + one[j] == M){
cout << i << " " << j << endl;
}
}
}
}
2.组成生成
2.1递归枚举
//recurise comb gen
const int M = 3;
int comb[M+1];
void genComb(int index,int start,int N){
if(index == M+1){
for(int i = 1 ; i <= M ; i++)
cout << comb[i] << " ";
cout << endl;
return;
}
for(int i = start ; N - i >= M - index ; i++){
comb[index] = i;
genComb(index+1,i+1,N);
}
}
2.2next生成法
寻找比当前组合大的那个最靠近的下一个组合：从右往左寻找第一个可以改变的位置值，从该位置值开始重新安排一个比它大1的值，可以安排到末尾。比如 C(5,3),2 3 5的下一个是 2 4 5。
//next gen comb
void nextComb(int n,int m){
int array[100];
for(int i = 1 ; i <= m ; i++)
array[i] = i;
while(true){
for(int i = 1 ; i <= m ; i++){
cout << array[i] << " ";
}
cout << endl;
int pos = -1;
for(int j = m ; j >= 1 ; j--){
if(array[j]+1+m-j <= n){
pos = j;
break;
}
}
if(pos == -1)break;
array[pos]++;
for(int j = pos+1 ; j <= m ; j++){
array[j] = array[j-1]+1;
}
}
}
3.利用01排列，转为排列的生成
3.1自己写next peru
方法：从右往左扫描，找到第一个下降点处停止，设为 a|b
该处将排列分成左右两部分，其中右半部分是单掉上升的。从右半部分找到大于a的最小值，将它与a交换，然后将右半部分翻转即可。比如 a|b...c...变成a|b...a...
正确性说明：注意交换后的b...a...仍然是单调上升的，因为c处是大于a的最小值，故原来c的右边必然小于a，左边大于a。交换a,c保证该排列变大，将其翻转保证是大于它的最小值。同时这个查找过程，保证了被增长的位置尽量靠右。
//next perm
void nextPerm(int N){
int array[100];
for(int i = 0 ; i < N ; i++){
array[i] = i+1;
}
while(true){
for(int j = 0 ; j < N ; j++)
cout << array[j] ;
cout << endl;
int pos = -1;
for(int i = N-2 ; i >= 0 ; i--){
if(array[i] < array[i+1]){
pos = i+1;
int min_pos = pos;
for(int j = pos ; j < N ; j++){
if(array[j] > array[i] && array[j] < array[min_pos]){
min_pos = j;
}
}
int temp = array[i];
array[i] = array[min_pos];
array[min_pos] = temp;
for(int j = pos,k = N-1 ; j < (N+pos)/2 ; j++,k--){
int temp = array[j];
array[j] = array[k];
array[k] = temp;
}
break;
}
}
if(pos == -1) break;
}
}
3.2利用c++库next_permutation
组合实际上可以看成是排列是01的特殊情况，故使用这个函数可以解决。
把数组元素赋恰当的0，1元素，直接调用next_permutation即可。
3.3递归生成排列
3.3.1无重复数字
//recur perm
void recurPerm(int array[],int index,int N){
if(index == N){
for(int i = 0 ; i < N ; i++)
cout << array[i];
cout << endl;
return;
}
for(int i = index ; i < N ; i++){
int temp = array[index];
array[index] = array[i];
array[i] = temp;
recurPerm(array,index+1,N);
temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
3.3.2含重复数字，表示采用a[i]表示i的个数的方法。
//recur perm 2
void recurPerm2(int a[],int size,int array[],int index,int N){
if(index == N){
for(int i = 0 ; i < N ; i++)
cout << array[i];
cout << endl;
return;
}
for(int i = 0 ; i < size ; i++){
if(a[i] > 0){
array[index] = i;
a[i]--;
recurPerm2(a,size,array,index+1,N);
a[i]++;
}
}
}
各函数调用方法：
int main(){
genComb(1,1,5);
enumComb(10,2);
nextComb(5,3);
nextPerm(3);
int array[4]={1,2,3,4};
recurPerm(array,0,4);
int a[2] = {2,2};
recurPerm2(a,2,array,0,4);
while(true);
}
评论