您的位置: 首页  >  文章  >  枚举排列的三种算法

枚举排列的三种算法

分类: 文章 • 2024-05-21 12:36:16

想不想打印所有排列？

输入整数n，按字典序从小到大输出前n个数的所有排列。

1 生成1~n的排列

伪代码：

void print_permutation(序列A,集合S)
{
    if(S为空) 输出序列A；
    else按照从小到大的顺序依次考虑S中的每个元素
    {
        print_permutation(在A的末尾添加v后得到的新序列，S-{v});
    }
}

下面考虑程序实现。用数组A表示序列A，集合S 不用保存，因为它可以有序列A 完全确定-A中没有出现的元素都可以选。

代码：

 1 void print_permutation(int n,int*A,int cur)
 2 {
 3     if(cur==n)//递归边界
 4     {
 5         for(int i = 0;i<n;i++)
 6         {
 7             cout << A[i] << " ";
 8         }
 9         cout << endl;
10     }
11     else
12     {
13         for(int i = 1;i<=n;i++)//尝试在A中填入各种整数i
14         {
15             int ok = 1;
16             for(int j = 0;j<cur;j++)
17             {
18                 if(A[j]==i)//如果i已经在A[0]~A[cur-1]出现过，则不能再选
19                 {
20                     ok = 0;
21                 }
22             }
23             if(ok)
24             {
25                 A[cur++] = i;
26                 print_permutation(n,A,cur);//递归调用
27                 cur--;
28             }
29         }
30     }
31 
32 }

循环变量i是当前考察的A[cur]，上面的程序用到了一个标志变量ok，来看i有没有在A中出现过，ok为1说明没有出现就可以把i加到A[cur]处

声明一个足够大的数组A，然后调用print_permutation(n,A,0);

2 生成可重集的序列

把问题改成输入数组P，并按字典序输出数组A各元素的所有全排列，则需要修改if(A[j]==i)为if(A[j]==P[i])，把A[cur]=i，改成A[cur]=P[i]。

但是如果P中有重复元素就会失效，因为上面的算法是看有无重合元素来判断P[i]在A[j]中出现过没有，来决定是不是添加P[i]；

可以统计A[0]~A[cur-1]中P[i]出现的次数c1，和P[i]在P数组中出现的次数c2，只要c1<c2，就能递归调用。

代码：

void print_permutation_2(int n,int*P,int*A,int cur)
{
    if(cur==n)
    {
        for(int i = 0;i<n;i++)
        {
            cout << A[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(A[j]==P[i])
                        c1++;
                for(int j = 0; j<n; j++)
                    if(P[i]==P[j])
                        c2++;
                int ok = 1;
                if(c1<c2)
                {
                    A[cur++] = P[i];
                    print_permutation_2(n,P,A,cur);
                    cur--;
                }
            }
        }
    }

}

3 解答树

递归函数的调用可用解答树来表示，

枚举排列的三种算法

第0层有n个孩子，第一层n-1个孩子，第二层n-2个孩子，...，第n层为叶节点没有孩子，每个叶子对应于一个排列，共n！个叶子。

如果某些问题的解可由多个步骤得到，而每个步骤都有若干种选择，可用递归算法实现，他的工作方式可由解答树描述。

一个重要结论：在多数情况下，解答树上的节点几乎全部来自于最后一两层。和他们相比，上面的节点数可以忽略不计。

4 下一个排列

代码：

 1 void print_permutation_3(int n,int* P)
 2 {
 3     sort(P,P+n);
 4     do{
 5         for(int i = 0;i<n;i++)
 6         {
 7             cout << P[i] << " ";
 8         }
 9         cout << endl;
10     }while(next_permutation(P,P+n));
11 }

 代码汇总：

枚举排列的三种算法枚举排列的三种算法
  1 #include <iostream>
  2 #include <algorithm>
  3 #define max_n 10005
  4 using namespace std;
  5 int A[max_n];
  6 int P[max_n];
  7 /*void print_permutation(序列A,集合S)
  8 {
  9     if(S为空) 输出序列A；
 10     else按照从小到大的顺序依次考虑S中的每个元素
 11     {
 12         print_permutation(在A的末尾添加v后得到的新序列，S-{v});
 13     }
 14 }*/
 15 void print_permutation(int n,int*A,int cur)
 16 {
 17     if(cur==n)//递归边界
 18     {
 19         for(int i = 0;i<n;i++)
 20         {
 21             cout << A[i] << " ";
 22         }
 23         cout << endl;
 24     }
 25     else
 26     {
 27         for(int i = 1;i<=n;i++)//尝试在A中填入各种整数i
 28         {
 29             int ok = 1;
 30             for(int j = 0;j<cur;j++)
 31             {
 32                 if(A[j]==i)//如果i已经在A[0]~A[cur-1]出现过，则不能再选
 33                 {
 34                     ok = 0;
 35                 }
 36             }
 37             if(ok)
 38             {
 39                 A[cur++] = i;
 40                 print_permutation(n,A,cur);//递归调用
 41                 cur--;
 42             }
 43         }
 44     }
 45 
 46 }
 47 void print_permutation_2(int n,int*P,int*A,int cur)
 48 {
 49     if(cur==n)
 50     {
 51         for(int i = 0;i<n;i++)
 52         {
 53             cout << A[i] << " ";
 54         }
 55         cout << endl;
 56     }
 57     else
 58     {
 59         for(int i = 0;i<n;i++)
 60         {
 61             if(!i||P[i]!=P[i-1])
 62             {
 63                 int c1 = 0,c2 = 0;
 64                 for(int j = 0; j<cur; j++)
 65                     if(A[j]==P[i])
 66                         c1++;
 67                 for(int j = 0; j<n; j++)
 68                     if(P[i]==P[j])
 69                         c2++;
 70                 int ok = 1;
 71                 if(c1<c2)
 72                 {
 73                     A[cur++] = P[i];
 74                     print_permutation_2(n,P,A,cur);
 75                     cur--;
 76                 }
 77             }
 78         }
 79     }
 80 
 81 }
 82 void print_permutation_3(int n,int* P)
 83 {
 84     sort(P,P+n);
 85     do{
 86         for(int i = 0;i<n;i++)
 87         {
 88             cout << P[i] << " ";
 89         }
 90         cout << endl;
 91     }while(next_permutation(P,P+n));
 92 }
 93 int main()
 94 {
 95     int P[]={1,2,4,3};
 96     //sort(P,P+4);
 97     //print_permutation_2(4,P,A,0);
 98     print_permutation_3(4,P);
 99     return 0;
100 }
View Code

 

相关推荐