排列与组合
先是一个递归的排列，顺便复习以下bitset的用法
//递归，保存当前状态的
#include <bitset>#include <stdio.h>using namespace std;const int NUM = 6;bitset<NUM> flag;char data[NUM];int order[NUM];void printPermut(int no);int main(){for(int i=0 ; i<NUM ; i++ ){data[i] = char('a'+i);}flag.set();printPermut(NUM);}void print(){for(int i=0 ; i<NUM ; i++ ){printf("%c",data[order[i]]);}printf("\n");}void printPermut(int no){for(int i = 0;i<NUM ;i++){if(flag.test(i)){order[NUM-no] = i;flag.flip(i);printPermut(no-1);flag.flip(i);}}if(no == 1)print();}?回一下bitset的方法
bitset例子
#include "stdafx.h"#include <iostream>#include <bitset>using namespace std;int _tmain(int argc, _TCHAR* argv[]){ bitset<32> bitvec(8);bool flag = bitvec.any();//判断是否存在某位或者多位为1,有则返回truebool flag1 = bitvec.none();//判断是否所有的位都是0，是则返回truebool flag2 = bitvec.test(3);//测试第4位是否为1，是则返回truecout<<"第4位为："<<bitvec[3]<<endl;//输出第4位的值bitvec.reset(3);//将第4位设置为0，或者bitvec[3] = 0cout<<"第4位为："<<bitvec[3]<<endl;//输出第4位的值bitvec.reset();//将所有位设置为0cout<<"bitvec的值为："<<bitvec.to_string()<<endl;bitvec.set();//将所有位设置为1cout<<"bitvec的值为："<<bitvec.to_string()<<endl;bitvec = 8;cout<<"bitvec的值为："<<bitvec.to_string()<<endl;bitvec.flip();//将所有的位翻转cout<<"bitvec的值为："<<bitvec.to_string()<<endl;bitvec.flip(0);//翻转第一位cout<<"bitvec的值为："<<bitvec.to_string()<<endl;bitvec = 0xffff;//设置低16位为1cout<<"bitvec的值为："<<bitvec.to_string()<<endl;bitvec = 012;//用八进制值012设置bitveccout<<"bitvec的值为："<<bitvec.to_string()<<endl;string bit = "1011";bitset<32> bitvec1(bit);//用字符串对象初始化bitset<32>对象cout<<"bitvec1的值为："<<bitvec1.to_string()<<endl;string bit1 = "1111110101100011010101";bitset<32> bitvec2(bit1,6);//用 从第6位开始到字符串结束 这一部分 初始化bitvec2 cout<<"bitvec2的值为："<<bitvec2.to_string()<<endl;bitset<32> bitvec3(bit1,6,4);//用 从第6位开始，长度为4 这一部分 初始化bitvec3;cout<<"bitvec3的值为："<<bitvec3.to_string()<<endl;} ?下面是一个非递归的算法，和上面的本来就不一样，因为上面的那种方法一开始没写出来非递归的。。。
交换的方法
#include <stdio.h> #include <stdlib.h> //排列与组合的非递归算法，排列是交换，组合是选择//从n个元素的数组a中，取m个元素的组合bool zuhe(int a[],int n,int m) {//p[x]=y 取到的第x个元素，是a中的第y个元素 int index,i,*p; p=(int*)malloc(sizeof(int)*m); if(p==NULL) return false; index=0; p[index]=0;//取第一个元素 while(true) { if(p[index]>=n) {//取到底了，回退 if(index==0) {//各种情况取完了，不能再回退了 break; } index--;//回退到前一个 p[index]++;//替换元素 } else if(index==m-1) {//取够了，输出 for(i=0;i<m;i++) { printf("%d,",a[p[i]]); } printf("\n"); p[index]++; //替换元素 } else {//多取一个元素 index++; p[index]=p[index-1]+1; } } free(p); return true;}//对n个元素的数组a，进行全排列bool pailie(char a[],int n){//p[x]=y 取到的第x个元素，是a中的第y个元素 int i,j,temp,*p; p=(int*)malloc(sizeof(int)*n); if(p==NULL) { return false; } for(i=0;i<n;i++) {//初始排列 p[i]=i; } while(true) {//循环m=n!次 //输出一种排列情况 for(i=0;i<n;i++) { printf("%c",a[p[i]]); } printf("\n"); //从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。 for(i=n-1;i>0 && p[i]<p[i-1];i--); //若没有后面的数大于前面的数的情况，说明已经到了最后一个排列，返回 if(i==0) break; //从后查到i，查找大于p[i - 1]的最小的数，记入j for(j=n-1;j>i && p[j]<p[i-1];j--); //交换p[i-1]和p[j] temp=p[i-1];p[i-1]=p[j];p[j]=temp; //倒置p[i]到p[n-1] for(i=i,j=n-1;i<j;i++,j--) {//交换p[c]和p[d] temp=p[i];p[i]=p[j];p[j]=temp; } } free(p); return true;}int main() { int a[]={1,2,3,4,5};char data[] = {'a','b','c','d','e','f'};zuhe(a,5,3); pailie(data,4);//排列 return 0;}??