生成可重集的排列 hdu 1716 排列2

1、生成1~n的排列

void print_permutation(int n,int A*,int cur)
{
    if(cur==n)
    {
        for(int i=0;i<n;++i)
            if(i!=n-1) printf("%d ",A[i]);
        printf("\n");
    }
    else
    {
        for(int i=1;i<=n;++i)
        {
            if(vis[i]) continue;
            else
            {
                vis[i]=1;
                A[cur]=i;
                print_permutation(n,A,cur+1);
                vis[i]=0;
            }
        }
    }
}

2、生成可重集的排列

输出格式真的是太经典了emmm

//A，神奇的输出格式
#include<iostream>
#include<algorithm>
using namespace std;
int s[4];
int ans[4];
int flag=0,sign;
int sign1;
void dfs(int cur)
{
    if(cur==4)
    {
        if(flag!=ans[0])                //看看和上一个千位是否相同
        {
            if(flag)                    //不相同，但是若flag=0，说明是第一行，前面没用空行，否则有空行
              cout<<endl;
            flag=ans[0];                //记录上一个答案的千位
            sign=0;
        }
        ++sign;
       if(sign!=1) cout<<" ";
       for(int i=0;i<4;++i)
         cout<<ans[i];
    }
    else
    {
        for(int i=0;i<4;++i)
        {
            if(!i||s[i]!=s[i-1])                                //不重不漏地枚举
            {
                int c1=0,c2=0;
                for(int j=0;j<cur;++j) if(ans[j]==s[i]) c1++;   //已经使用掉的s[i]数量
                for(int j=0;j<4;++j) if(s[j]==s[i]) c2++;       //总共有的s[i]数量
                if(!cur)                                        //如果是千位数的首位
                {
                    if(!s[i]||c1==c2) continue;                 //是0或者没有位置了，告辞
                    ans[cur]=s[i];  //
                    dfs(cur+1);
                }
                else if(c1<c2)
                {
                    ans[cur]=s[i];
                    dfs(cur+1);
                }

            }
        }
    }
}
int main()
{
    sign1=0;
    while(cin>>s[0]>>s[1]>>s[2]>>s[3])
    {
        if(!s[0]&&!s[1]&&!s[2]&&!s[3])
            break;
        sign1++;
        if(sign1!=1) cout<<endl;        //每一个样例前面一个空行
        flag=0,sign=0;
        sort(s,s+4);
        dfs(0);
        cout<<endl;
    }
}

stl版本  ->记录上一个是啥以保证和上一个是否一样的思路经常用

每新换一行sign就更新，标记是否是该行的第一组

void perm()         //next_permutation函数生成的是不重复的集合
{
    do
    {
        if(!s[0]) continue;                     //千位是0，不OK
        if(flag!=s[0])
        {
            if(flag) cout<<endl;                //新的开头，新的一行
            flag=s[0];
            sign=0;
        }
        ++sign;
        if(sign!=1) cout<<' ';
        for(int i=0;i<4;++i) cout<<s[i];
    }while(next_permutation(s,s+4));
}
int main()
{
    sign1=0;
    while(cin>>s[0]>>s[1]>>s[2]>>s[3])
    {
        if(!s[0]&&!s[1]&&!s[2]&&!s[3])
            break;
        sign1++;
        if(sign1!=1) cout<<endl;        //每一个样例前面一个空行
        flag=0,sign=0;
        sort(s,s+4);
        perm();
       // dfs(0);
        cout<<endl;
    }
}