排列与组合

先是一个递归的排列，顺便复习以下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;}

?