全排列的系列问题总结-一一网

这是我参与更文挑战的第5天，活动详情查看：更文挑战

全排列问题

在这里插入图片描述

递归分析

•用一个数组a[n]来保存1~~n之间的n个自然数，对于i=1~~n，每次用a[1]与a[i]交换后，对a[2]~a[n]中的n-1个元素进行全排列

说明：大家轮流来做第1个，→ 循环 + 交换。确定好第1个后，对剩下的n-1个再进行全排列→递归

•然后交换a[1]与a[i]的值，使它恢复到此次排列前的状态

已经做过第一个了，请回到原地，轮到下一个当第一个了。

确定好了第一个之后，从剩下的n-1个中轮流选一个来做第2个 → 循环 + 交换，确定好了第二个之后，从剩下的n-2个再进行全排列。直到只有一个素的时候，全排列就是自己。

inline void perm(int list[], int k, int n)//求list数组 第k个到第n的全排列。
{
    int i, t;
    if (k == n)
    {
        for (i = 0; i <= n; i++)
        {
            printf("%d", list[i]);
        }
        printf("\n");
    }

    for (i = k; i <= n; i++)
    {
        swap(list[k], list[i]);
        perm(list, k + 1, n); //求k+1~n的全排列
        swap(list[k], list[i]);
    }
}
复制代码

字典序

全排列生成算法的一个重要思路，就是将集合A中的元素的排列，与某种顺序建立一一映射的关系，按照这种顺序，将集合的所有排列全部输出。这种顺序需要保证，既可以输出全部的排列，又不能重复输出某种排列，或者循环输出一部分排列。字典序就是用此种思想输出全排列的一种方式。这里以A{1,2,3,4}来说明用字典序输出全排列的方法。

首先，对于集合A的某种排列所形成的序列，字典序是比较序列大小的一种方式。以A{1,2,3,4}为例，其所形成的排列1234<1243，比较的方法是从前到后依次比较两个序列的对应元素，如果当前位置对应元素相同，则继续比较下一个位置，直到第一个元素不同的位置为止，元素值大的元素在字典序中就大于元素值小的元素。上面的a1[1…4]=1234和a2[1…4]=1243，对于i=1,i=2，两序列的对应元素相等，但是当i=2时，有a1[2]=3<a2[2]=4，所以1234<1243。

使用字典序输出全排列的思路是，首先输出字典序最小的排列，然后输出字典序次小的排列，……，最后输出字典序最大的排列。这里就涉及到一个问题，对于一个已知排列，如何求出其字典序中的下一个排列。这里给出算法。

对于排列a[1…n]，找到所有满足a[k]<ak+1的k的最大值，如果这样的k不存在，则说明当前排列已经是a的所有排列中字典序最大者，所有排列输出完毕。
在a[k+1…n]中，寻找满足这样条件的元素l，使得在所有a[l]>a[k]的元素中，a[l]取得最小值。也就是说a[l]>a[k]，但是小于所有其他大于a[k]的元素。
交换a[l]与a[k].
对于a[k+1…n]，反转该区间内元素的顺序。也就是说a[k+1]与a[n]交换，a[k+2]与a[n-1]交换，……，这样就得到了a[1…n]在字典序中的下一个排列。

在这里插入图片描述

int arry[3] = { 1,2,2 };//len==3;  
      //重复序列会去除
    void Permutation()  
    {  
        int len = 3;  
        int j, k;  
      
        while (true)  
        {  
            printf("%d%d%d\n", arry[0], arry[1], arry[2]);  
      
            for (j = len - 2; j >= 0 && arry[j] >= arry[j + 1]; j--);//注意此处 j >= 0 判断条件在前,加个等号即可  
      
            if (j < 0) return;//结束  
      
            for (k = len - 1; k > j&&arry[k] <= arry[j]; k--);//加个等号即可  
      
            swap(arry[k], arry[j]);  
      
            for (int l = j + 1, r = len - 1; l < r; l++, r--)  
                swap(arry[l], arry[r]);  
           
        }  
    }  

复制代码

从原理到应用

我们已经知道了实现原理，现在来说一下使用吧，

不知道大家是否还记得STL—“algorithm” 中的两个函数next_permutation和prev_permutation

next_permutation: 对于当前的排列，如果在字典序中还存在下一个排列，返回真，并且将下一个排列赋予当前排列，如果不存在，就把当前排列进行递增排序。

prev_permutation: 对于当前的排列，如果在字典序中还存在前一个排列，返回真，并且将前一个排列赋予当前排列，如果不存在，就把当前排列进行递减排序。

    #include<iostream>  
    #include<algorithm>  
      
    using namespace std;  
      
    int arry[3] = { 1,2,3 };//len==3;  
      
    void Permutation()  
    {  
        do  
            printf("%d%d%d\n", arry[0], arry[1], arry[2]);  
        while (next_permutation(arry, arry + 3));  
          
    }  
      
    int main()  
    {  
      
        Permutation();  
      
        return 0;  
    }  
复制代码