枚举排列

排列

在暴力求解中，常常通过枚举所有的可能排列来得到答案，所有如何生成所有的排列也就十分重要。

生成1~n的排列

采用递归的思想，从前往后逐位进行考虑。

 1 //1~n的全排列（字典序）
 2 void permutation(int n, int *A, int cur)
 3 {
 4     if (cur == n)
 5     {
 6         for (int i = 0; i < n; i++)  printf("%d%c", A[i], i == n - 1 ? '
' : ' ');
 7     }
 8     else for (int i = 1; i <= n; i++) {
 9         int ok = 1;
10         for (int j = 0; j < cur; j++)
11             if (A[j] == i)  ok = 0;
12         if (ok)
13         {
14             A[cur] = i;
15             permutation(n, A, cur + 1);
16         }
17     }
18 }

其实上面这个为了保证字典序，时间复杂度实际变成O(nⁿ)。

可重集的排列

即待排列的数组中有相同的元素，得到所有的排列。

//可重集的排列
//若要字典序，需要保证P有序
void permutation(int n,int *P, int *A, int cur)
{
    if (cur == n)
    {
        for (int i = 0; i < n; i++)  printf("%d%c", A[i], i == n - 1 ? '
' : ' ');
    }
    else for (int i = 0; i < n; i++) {
        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++;　　　　//可以预处理
        if (c1 < c2)
        {
            A[cur] = P[i];
            permutation(n, P, A, cur + 1);
        }
    }
}

实际上，若不要求字典序，可将时间复杂度降为O(n!)

 1 //打印出a数组的全排列（非字典序）
 2 void permutation(int *a,int n,int cur)
 3 {
 4     if (cur == n)
 5     {
 6         for (int i = 0; i < n; i++)
 7             printf("%d%c", a[i], i == n - 1 ? '
' : ' ');
 8         return;
 9     }
10     for (int i = 0; i < n - cur; i++) //提取待排数组中的每一个元素
11     {
12         swap(a[cur], a[cur + i]);　　//第cur个与cur之后的元素交换
13         permutation(a,n,cur + 1);
14         swap(a[cur], a[cur + i]);　　//还原
15     }
16 }

它还有一些好处，不必开辟存储结果的数组，也可用来生成可重集的排列。

下一个排列

枚举所有排列的另一个方法是从字典序最小的排列开始，不停调用“求下一个排列”的过程。C++的STL中提供了一个库函数next_permutation来求下一个排列。

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 10;
 7 int n, a[maxn];
 8 
 9 int main()
10 {
11 
12     scanf("%d", &n);
13     for (int i = 0; i < n; i++)  scanf("%d", &a[i]);
14     sort(a, a + n);　　　　　　　　　　//得到p的最小排列
15     do
16     {
17         for (int i = 0; i < n; i++)  printf("%d%c", a[i], i == n - 1 ? '
' : ' ');
18     } while (next_permutation(a,a + n));  　　//求下一个排列
19 
20     return 0;
21 }