閱讀502 返回首頁    go 阿裏雲 go 技術社區[雲棲]

全排列生成算法 .

參考鏈接: 全排列生成算法（一）
原文講的很詳細了，為了完整性，這裏粘貼的參考鏈接中大部分文字，並且在原文的基礎上，添加了“給定某個排列，求其字典序中上一個元素”的算法。

字典序

全排列生成算法的一個重要思路，就是將集合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]<a[k+1](0<k<n-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]在字典序中的下一個排列。
這裏我們以排列a[1...8]=13876542為例，來解釋一下上述算法。首先我們發現，1(38)76542，括號位置是第一處滿足a[k]<a[k+1]的位置，此時k=2。所以我們在a[3...8]的區間內尋找比a[2]=3大的最小元素，找到a[7]=4滿足條件，交換a[2]和a[7]得到新排列14876532，對於此排列的3～8區間，反轉該區間的元素，將a[3]-a[8]，a[4]-a[7]，a[5]-a[6]分別交換，就得到了13876542字典序的下一個元素14235678。

求字典序的上一個全排列：
從前麵的的分析，我們可以進行逆推導，求得上一個排列，這裏的算法如下：
1. 對於排列a[1..n],從尾端開始，找到第一個a[k]>a[k+1]並記錄，若k<0，則說明a已經是字典序的最小者。
2. 在a[k+1..n]中，尋找小於a[k]的最大元素a[i]，
3. 交換a[k]和a[i]的值，
4. 對於a[k+1..n]，反轉區間內元素的順序。
這裏我們還是以前麵的例子來說明，初始時，a=14235678，首先找到1(42)35678，此時k=2，再找到比4小的最大數是3，此時a[i]=3, i=4, 交換a[i]和a[k]的值，得到a=13245678，最後反轉a[k+1..n]，得到最後的結果a=13876542。

C代碼如下：
  1. /* 
  2. https://t.jobdu.com/thread-98707-1-1.html 
  3. 1、寫出一個算法來生成1-n的全排列 
  4. 2、已知一個長度為N的序列A，它的每個元素是1-N之間的任何一個元素，且兩兩不重複，稱他為一個排列，寫出一個算法生成該排列的字典序的下一排列。例如，A=[3 2 1 4]，則下一排列為A'=[3 2 4 1]，A'的下一排列為A''=[3 4 1 2]，以此類推。 
  5. https://blog.csdn.net/joylnwang/article/details/7064115 
  6. */  
  7.   
  8. #include <stdio.h>   
  9.   
  10. void swap(char* array, unsigned int i, unsigned int j)  
  11. {  
  12.     char t = array[i];  
  13.     array[i] = array[j];  
  14.     array[j] = t;  
  15. }  
  16.   
  17. // 遞歸輸出序列的全排列   
  18. void fullPermutation(char* arr, int len, int index)  
  19. {  
  20.     int i;  
  21.     if (index >= len)  
  22.         printf("%s\n", arr);  
  23.     else  
  24.     {  
  25.         for (i = index; i < len; i++)  
  26.         {  
  27.             swap(arr, index, i);  
  28.             fullPermutation(arr, len, index+1);  
  29.             swap(arr, index, i);  
  30.         }  
  31.     }  
  32. }  
  33.   
  34. void reverse(char arr[], int start, int end)  
  35. {  
  36.     if (start >= end)  
  37.         return;  
  38.     int len = start - end + 1;  
  39.     int i;  
  40.     for (i = 0; i <= len/2; i++)  
  41.     {  
  42.         swap(arr, start+i, end-i);  
  43.     }  
  44. }  
  45.   
  46. int pre_permutation(char arr[], int len)  
  47. {  
  48.     int k, i, max, max_i;  
  49.     for (i = len-2; i >= 0; i--)  
  50.     {  
  51.         if (arr[i] > arr[i+1])  
  52.         {  
  53.             k = i;  
  54.             break;  
  55.         }  
  56.     }  
  57.     if (i < 0)  
  58.     {  
  59.         printf("%s is the first permutation\n", arr);  
  60.         return -1;  
  61.     }  
  62.     max_i = k + 1;  
  63.     max = arr[max_i];  
  64.     for (i = k+1; i < len; i++)  
  65.     {  
  66.         if (arr[i] < arr[k] && arr[i] > max)  
  67.         {  
  68.             max_i = i;  
  69.             max = arr[max_i];  
  70.         }  
  71.     }  
  72.     if (max_i < len)  
  73.     {  
  74.         swap(arr, k, max_i);  
  75.         reverse(arr, k+1, len-1);  
  76.     }  
  77.     return 0;  
  78. }  
  79.   
  80. int next_permutation(char arr[], int len)  
  81. {  
  82.     int k, i, min, min_i;  
  83.     for (k = len-2; k >= 0; k--)  
  84.     {  
  85.         if (arr[k] < arr[k+1])  
  86.             break;  
  87.     }  
  88.     if (k < 0)  
  89.     {  
  90.         printf("%s is the last permutation\n", arr);  
  91.         return -1;  
  92.     }  
  93.     min = arr[k+1];  
  94.     min_i = k+1;  
  95.     for (i = k + 1; i < len; i++)  
  96.     {  
  97.         if (arr[i] > arr[k] && arr[i] < min)  
  98.         {  
  99.             min_i = i;  
  100.             min = arr[i];  
  101.         }  
  102.     }  
  103.     if (min_i < len)  
  104.     {  
  105.         swap(arr, k, min_i);  
  106.         reverse(arr, k+1, len-1);  
  107.     }  
  108.     return 0;  
  109. }  
  110.   
  111. int main()  
  112. {  
  113.     int i = 1;  
  114.     char arr[] = "1234";  
  115.     int len = sizeof(arr) / sizeof(arr[0]) - 1;  
  116.     //fullPermutation(arr, len, 0); // 遞歸打印全排列   
  117.   
  118.     // 按照字典序輸出全排列   
  119.     printf("next_permutation demo:\n");  
  120.     do  
  121.     {  
  122.         printf("%02d: %s\n", i, arr);  
  123.         i++;  
  124.     } while (next_permutation(arr, len) >= 0);  
  125.   
  126.     i = 1;  
  127.     printf("\npre_permutation demo:\n");  
  128.     do  
  129.     {  
  130.         printf("%02d: %s\n", i, arr);  
  131.         i++;  
  132.     }  
  133.     while (pre_permutation(arr, len) >= 0);  
  134.   
  135.     return 0;  
  136. }  
/*
https://t.jobdu.com/thread-98707-1-1.html
1、寫出一個算法來生成1-n的全排列
2、已知一個長度為N的序列A，它的每個元素是1-N之間的任何一個元素，且兩兩不重複，稱他為一個排列，寫出一個算法生成該排列的字典序的下一排列。例如，A=[3 2 1 4]，則下一排列為A'=[3 2 4 1]，A'的下一排列為A''=[3 4 1 2]，以此類推。
https://blog.csdn.net/joylnwang/article/details/7064115
*/

#include <stdio.h>

void swap(char* array, unsigned int i, unsigned int j)
{
    char t = array[i];
    array[i] = array[j];
    array[j] = t;
}

// 遞歸輸出序列的全排列
void fullPermutation(char* arr, int len, int index)
{
    int i;
    if (index >= len)
        printf("%s\n", arr);
    else
    {
        for (i = index; i < len; i++)
        {
            swap(arr, index, i);
            fullPermutation(arr, len, index+1);
            swap(arr, index, i);
        }
    }
}

void reverse(char arr[], int start, int end)
{
    if (start >= end)
        return;
    int len = start - end + 1;
    int i;
    for (i = 0; i <= len/2; i++)
    {
        swap(arr, start+i, end-i);
    }
}

int pre_permutation(char arr[], int len)
{
    int k, i, max, max_i;
    for (i = len-2; i >= 0; i--)
    {
        if (arr[i] > arr[i+1])
        {
            k = i;
            break;
        }
    }
    if (i < 0)
    {
        printf("%s is the first permutation\n", arr);
        return -1;
    }
    max_i = k + 1;
    max = arr[max_i];
    for (i = k+1; i < len; i++)
    {
        if (arr[i] < arr[k] && arr[i] > max)
        {
            max_i = i;
            max = arr[max_i];
        }
    }
    if (max_i < len)
    {
        swap(arr, k, max_i);
        reverse(arr, k+1, len-1);
    }
    return 0;
}

int next_permutation(char arr[], int len)
{
    int k, i, min, min_i;
    for (k = len-2; k >= 0; k--)
    {
        if (arr[k] < arr[k+1])
            break;
    }
    if (k < 0)
    {
        printf("%s is the last permutation\n", arr);
        return -1;
    }
    min = arr[k+1];
    min_i = k+1;
    for (i = k + 1; i < len; i++)
    {
        if (arr[i] > arr[k] && arr[i] < min)
        {
            min_i = i;
            min = arr[i];
        }
    }
    if (min_i < len)
    {
        swap(arr, k, min_i);
        reverse(arr, k+1, len-1);
    }
    return 0;
}

int main()
{
    int i = 1;
    char arr[] = "1234";
    int len = sizeof(arr) / sizeof(arr[0]) - 1;
    //fullPermutation(arr, len, 0); // 遞歸打印全排列

    // 按照字典序輸出全排列
    printf("next_permutation demo:\n");
    do
    {
        printf("%02d: %s\n", i, arr);
        i++;
    } while (next_permutation(arr, len) >= 0);

    i = 1;
    printf("\npre_permutation demo:\n");
    do
    {
        printf("%02d: %s\n", i, arr);
        i++;
    }
    while (pre_permutation(arr, len) >= 0);

    return 0;
}


最後更新：2017-04-03 20:57:46

  上一篇：go 抓包分析360瀏覽器和360搜索配對使用的安全性
  下一篇：go iOS網絡編程-iOS中Socket編程介紹