Review DFS-Permutation-Combination-NextPermutation

7月 19 2014

今天看到一道next_permutation的题目，于是打算串一下之前写的基于DFS或者backtrack的permutation和combination算法，顺便回顾了MS实习的一道题

突然发现next_permutation自己好像还不会，手动实现，而combination的下一个字典序当初也是直接调用next_permutation的。。。

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iomanip>
#include <unordered_set>
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
using namespace std;

void permutation(int k, int n, int*a)
{
    if(k==n)
    {
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int i=k;i<=n-1;i++)
        {
            swap(a[k],a[i]);
            permutation(k+1,n,a);
            swap(a[k],a[i]);
        }
    }
}

void combination(bool* select, int selectk, int k, int selectn, int n, int*a, int &count, int K)
{
    if(selectn==n)
    {
        if(selectk==k)
        {
            count++;
            if(count==K)
            {
                for(int i=0;i<n;i++)
                {
                    if(select[i])
                    {
                        cout<<"1";
                    }
                    else
                        cout<<"0";
                }
                cout<<endl;
            }
        }
    }
    else
    {
        select[selectn]=false;
        combination(select,selectk,k,selectn+1,n,a,count,K);
        select[selectn]=true;
        combination(select,selectk+1,k,selectn+1,n,a,count,K);

    }
}

int main()
{
    read;
    //write;
    int a[]={1,2,3,4,5};
    //permutation(0,5,a);
    bool select[100];
    memset(select,0,sizeof(bool)*10);

    int N,M,K,count=0;
    while(cin>>N>>M>>K)
    {
        string str;
        for(int i=0;i<N;i++)
            str+='0';
        for(int i=0;i<M;i++)
            str+='1';
        int i=1;
        while(i<K)
        {
            bool has=next_permutation(str.begin(),str.end());
            if(has==false) 
                break; 
            i++;
        }
        if(i<K)
            cout<<"Impossible"<<endl;
        else
            cout<<str<<endl;
        /*
        count=0;
        combination(select,0,M,0,N+M,a,count,K);
        if(count<K)
            cout<<"Impossible"<<endl;
            */
    }


return 0;

}
分别用next_permutaion和自己手写的combination来实现 kth 01 string, C(n,k)这个会复杂些，参数比较多，我还用了一个count引用参数传递，这样是不好的，参数多了可能会有溢出的风险，或者定义全局变量也是一样的。
然后记住next_permutation如果回到头了，会返回一个false其他都是返回true。还有传入的k是M的话(1的个数)那么需要注意内部select true为1，false为0，如果传入N的话，就反过来。然后递归出口，我一直都是这么写的，也没有剪枝，
搜完整个2^(N+M)的空间，之前剪枝好像逻辑出了点问题，就不敢剪了。。。。

另外有一点就是，int*a, a+1其实会自动地址值+4，自动定位到数组中下一个元素的地址

Posted by richard爱闹 - 7月 19 2014
如需转载，请注明：本文来自 Richard

留言