排列与组合

先是一个递归的排列，顺便复习以下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,有则返回true
	bool flag1 = bitvec.none();//判断是否所有的位都是0，是则返回true
	bool flag2 = bitvec.test(3);//测试第4位是否为1，是则返回true
	cout<<"第4位为："<<bitvec[3]<<endl;//输出第4位的值
	bitvec.reset(3);//将第4位设置为0，或者bitvec[3] = 0
	cout<<"第4位为："<<bitvec[3]<<endl;//输出第4位的值
	bitvec.reset();//将所有位设置为0
	cout<<"bitvec的值为："<<bitvec.to_string()<<endl;
	bitvec.set();//将所有位设置为1
	cout<<"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位为1
	cout<<"bitvec的值为："<<bitvec.to_string()<<endl;
	bitvec = 012;//用八进制值012设置bitvec
	cout<<"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;	
}