字典序全排列算法研究 - pmars－IT工程師數位筆記本

文章出處

　　最近對數學方面很有興趣，周末和同學去大學蹭課，其中在講排列組合的時候講到了全排列的字典序生成算法，我覺得這個想法真的挺好，去網上找了找，貌似都是遞歸求全排列，沒有講到這個算法的，今天我將這個算法寫出來了，發在這里，以后學習。

　　非遞歸方法（字典序法）：

　　這種算法被用在了C++的STL庫中。

　　對給定的字符集中的字符規定了一個先后關系，在此基礎上規定兩個全排列的先后是從左到右逐個比較對應的字符的先后。

　[例]字符集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:

     　　　　123,132,213,231,312,321

　　※ 一個全排列可看做一個字符串，字符串可有前綴、后綴。

　　生成給定全排列的下一個排列.所謂一個的下一個就是這一個與下一個之間沒有其他的。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。

 [例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個了。否則找出第一次出現下降的位置。

 【例】 一般而言，設P是[1,n]的一個全排列。
　　　　　　P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn
　　　　find:　　j=max{i|Pi<Pi+1}
　　　　　　　　　k=max{i|Pi>Pj}
　　　　　　1，  對換Pj，Pk，
　　　　　　2，  將Pj+1…Pk-1PjPk+1…Pn翻轉
          P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一個

【例】 如何得到346987521的下一個
    1，從尾部往前找第一個P(i-1) < P(i)的位置
            3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
        最終找到6是第一個變小的數字，記錄下6的位置i-1
    2，從i位置往后找到最后一個大于6的數
            3 4 6 -> 9 -> 8 -> 7 5 2 1
        最終找到7的位置，記錄位置為m
    3，交換位置i-1和m的值
            3 4 7 9 8 6 5 2 1
    4，倒序i位置后的所有數據
            3 4 7 1 2 5 6 8 9
    則347125689為346987521的下一個排列

　　依照上面的講述不難將代碼寫出來，如下：

        private static void PermutationList()
        {
            int fromIndex, endIndex, changeIndex;
            Sort(0, length - 1);
            do
            {
                // 輸出一種全排列
                Output();
                fromIndex = endIndex = length - 1;
                // 向前查找第一個變小的元素
                while (fromIndex > 0 && words[fromIndex] < words[fromIndex - 1]) --fromIndex;
                changeIndex = fromIndex;
                if (fromIndex == 0) break;
                // 向后查找最后一個大于words[fromIndex-1]的元素
                while (changeIndex + 1 < length && words[changeIndex + 1] > words[fromIndex - 1]) ++changeIndex;
                Swap(fromIndex - 1, changeIndex);   // 交換兩個值
                InvertArray(fromIndex, endIndex);   // 對后面的所有值進行反向處理
            } while (true);
        }

　　遞歸方法求全排列：

　　遞歸方法很容易理解：分別將每個位置交換到最前面位，之后全排列剩下的位。

【例】遞歸全排列 1 2 3 4 5
    1，for循環將每個位置的數據交換到第一位
            swap(1,1~5)
    2，按相同的方式全排列剩余的位

　　由于遞歸方法很容易理解，而且網上也有很多的資料，所以不過多講述，代碼如下：

        /// <summary>
        /// 遞歸方式生成全排列的方法
        /// </summary>
        /// <param name="fromIndex">全排列的起始位置</param>
        /// <param name="endIndex">全排列的終止位置</param>
        private static void PermutationList(int fromIndex, int endIndex)
        {
            if (fromIndex == endIndex)
                Output();
            else
            {
                for (int index = fromIndex; index <= endIndex; ++index)
                {
                    // 此處排序主要是為了生成字典序全排列，否則遞歸會打亂字典序
                    Sort(fromIndex, endIndex);
                    Swap(fromIndex, index);
                    PermutationList(fromIndex + 1, endIndex);
                    Swap(fromIndex, index);
                }
            }
        }

以上代碼只截取了部分關鍵代碼，所有代碼如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms
{
    class Permutation
    {
        private static int MAXLENGTH = 20;

        private static int length;
        private static char[] words = new char[MAXLENGTH];

        private static void Swap(int indexX, int indexY)
        {
            if (indexX != indexY)
            {
                char ch = words[indexX];
                words[indexX] = words[indexY];
                words[indexY] = ch;
            }
        }

        private static void InvertArray(int fromIndex, int endIndex)
        {
            for (; fromIndex < endIndex; ++fromIndex, --endIndex)
                Swap(fromIndex, endIndex);
        }

        private static void Sort(int fromIndex, int endIndex)
        {
            Array.Sort(words, fromIndex, endIndex - fromIndex + 1);
        }

        private static void Output()
        {
            for (int index = 0; index < length; ++index)
                Console.Write(words[index] + " ");
            Console.WriteLine();
        }

        private static void PermutationList()
        {
            int fromIndex, endIndex, changeIndex;
            Sort(0, length - 1);
            do
            {
                // 輸出一種全排列
                Output();
                fromIndex = endIndex = length - 1;
                // 向前查找第一個變小的元素
                while (fromIndex > 0 && words[fromIndex] < words[fromIndex - 1]) --fromIndex;
                changeIndex = fromIndex;
                if (fromIndex == 0) break;
                // 向后查找最后一個大于words[fromIndex-1]的元素
                while (changeIndex + 1 < length && words[changeIndex + 1] > words[fromIndex - 1]) ++changeIndex;
                Swap(fromIndex - 1, changeIndex);   // 交換兩個值
                InvertArray(fromIndex, endIndex);   // 對后面的所有值進行反向處理
            } while (true);
        }

        /// <summary>
        /// 遞歸方式生成全排列的方法
        /// </summary>
        /// <param name="fromIndex">全排列的起始位置</param>
        /// <param name="endIndex">全排列的終止位置</param>
        private static void PermutationList(int fromIndex, int endIndex)
        {
            if (fromIndex == endIndex)
                Output();
            else
            {
                for (int index = fromIndex; index <= endIndex; ++index)
                {
                    // 此處排序主要是為了生成字典序全排列，否則遞歸會打亂字典序
                    Sort(fromIndex, endIndex);
                    Swap(fromIndex, index);
                    PermutationList(fromIndex + 1, endIndex);
                    Swap(fromIndex, index);
                }
            }
        }

        public static void PermutationTest()
        {
            Console.Write("please input the permutation words:");
            words = Console.ReadLine().ToCharArray();
            length = words.Count();
            PermutationList();
            Console.ReadLine();
        }
    }
}