排列题目及其常见变形

系统管理员 2021-12-17 03:17 223阅读 0赞

**对一些数的排列和组合在编程中是非常常用的，现在对全排列及其一些变形总结到这儿 。**

**其实也就是深搜的思想，深搜得到一颗搜索树，然后在上面做一些题目要求的操作。**

\*\*给出一个数n，打印1-n形成的一个全排列

#include <iostream>
    using namespace std;
    int a[50];
    
    void print_permutation(int n,int *s,int cur)
    {
        if(cur==n)   ///打印
        {
            for(int i=0;i<n;i++)
            {
                if(i==n-1)
                    cout<<s[i];
                else
                    cout<<s[i]<<" ";
            }
            cout<<endl;
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                int ok=1;
                for(int j=0;j<cur;j++)   //枚举没有出现的
                {
                    if(s[j]==i) ok=0;
                }
                if(ok)
                {
                    s[cur]=i;
    
                    print_permutation(n,s,cur+1);  ///递归
                }
            }
        }
    }
    int main()
    {
        int T,n;
        cin>>T;
        while(T--)
        {
            cin>>n;
            print_permutation(n,a,0);
        }
        return 0;
    }

**\*\*用STL中next\_permutation 实现**

#include <iostream>
    #include <algorithm>
    using namespace std;
    int a[50];
    
    int main()
    {
        int T,n;
        cin>>T;
        while(T--)
        {
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                cin>>a[i-1];
            }
            do
            {
                for(int i=0;i<n;i++)
                {
                    if(i==n-1)
                        cout<<a[i];
                    else
                        cout<<a[i]<<" ";
                }
                cout<<endl;
            }while(next_permutation(a,a+n));
        }
        return 0;
    }

**\*\*通过递归实现形成一个排列树，打印任意数的全排列**

#include <iostream>
    #include <algorithm>
    using namespace std;
    int a[50];
    
    
    void print_permutation(int n,int *p,int *s,int cur)
    {
        if(cur==n)    //打印结果
        {
            for(int i=0;i<n;i++)
            {
                cout<<s[i]<<" ";
            }
            cout<<endl;
        }
        else
        {
            for(int i=0;i<n;i++)
            if(!i || p[i] != p[i-1])
            {
                int c1=0,c2=0;
                for(int j=0;j<cur;j++)
                {
                    if(s[j]==p[i]) c1++;
                }
                for(int j=0;j<n;j++)
                {
                    if(p[i]==p[j]) c2++;
                }
                if(c1<c2)
                {
                    s[cur]=p[i];
                    print_permutation(n,p,s,cur+1);
                }
            }
        }
    }
    int main()
    {
        int p[50];
        int T,n;
        cin>>T;
        while(T--)
        {
            cin>>n;
            for(int i=0;i<n;i++)
            cin>>p[i];
            sort(p,p+n);
            print_permutation(n,p,a,0);
        }
        return 0;
    }
    
    /***
    5
    4
    5 7 8 9
    5
    4 4 5 6 8
    ***/

**\*\* 变形，求出 [ nyoj469][nyoj469]**[擅长排列的小明 II][nyoj469]

1、第一个数必须是1

2、相邻两个数之差不大于2

满足这两个条件的一个1 -- n 的全排列 。用上面的方法肯定超时，其实是一个公式：a\[56\] = \{0,1,1,2\}; a\[i\] = a\[i-1\] + a\[i-3\] + 1;

**\*\*变形，求出1 -- n中选出 m 个数字让他继续全排列 [ nyoj19擅长排列的小明][nyoj19]**

#include <iostream>
    using namespace std;
    int a[50];
    
    void print_permutation(int m,int n,int *s,int cur)
    {
        if(cur==m)   ///打印
        {
            for(int i=0;i<m;i++)
            {
                cout<<s[i];
            }
            cout<<endl;
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                int ok=1;
                for(int j=0;j<cur;j++)   //枚举没有出现的
                {
                    if(s[j]==i+1) ok=0;
                }
                if(ok)
                {
                    s[cur]=i+1;
                    print_permutation(m,n,s,cur+1);  ///递归
                }
            }
        }
    }
    int main()
    {
        int T,n,m;
        cin>>T;
        while(T--)
        {
            cin>>n>>m;
            print_permutation(m,n,a,0);
        }
        return 0;
    }

[nyoj469]: http://acm.nyist.net/JudgeOnline/problem.php?pid=469
[nyoj19]: http://acm.nyist.net/JudgeOnline/problem.php?pid=19