全排列的遞歸實現方法

對于全排列，比如有5個字符abcde，則有5!=120種方法.

首先分析出數學遞歸公式,加上對abcde這個字符串中的字符做全排列。

那么,假設abcde是一個輸入參數，輸出的值則是一個全排列集合。我們就可以有：

f(abcde)=a+f(bcde) //注意，此處的+號不是簡單的加號，而是另一個運算規則，下面會說到。

f(bcde)=b+f(cde)

f(cde)=c+f(de)

f(de)={de,ed}

以上就是運算的遞歸函數，其中f()函數返回的是一集合，而這里的加號，筆者把它的行為定義為，把一個字符按順序的插入到一個字符串中。

舉個例子：

a+bcde，行為就是把a插在每個位置之間，得到的是如下的一個集合：

abcde,bacde,bcade,bcdae,bcdea

上面是a對單個項進行+操作。

a+f(bcde)則意思是a對一個集合f(bcde)做操作，意味著a對集合中每一個象做+操作。

如上的例子，a對bcde做操作會生成5個項的集合，那么事實上bcde的全排列，根據中學的數學計算推斷有4!就是24，f(bcde)有24個項。所以a+f(bcde)意味著a對于這24個項中的每一個項做操作，每個操作生成5個項的，因此總的就會生成5*24=120個項的集合。說到這，你就應該理解+操作的定義了。

事實上，寫成+操作只是為了看起來方便，也可以換種表的方式，比如叫做C操作，那么，上述遞歸的式子也可以寫成，

f(abcde)=C(a,f(bcde) )

f(bcde)=C(b,f(cde))

f(cde)=C(c,f(de))

f(de)={de,ed}

這兩種表達的數學含義都是一樣的。

有了數學意義的表達式，就可以寫代碼了

c#實現。

using System;   
using System.Collections.Generic;   
using System.Linq;   
using System.Text;  
 
namespace quanpailie   
{   
    class Program   
    {   
        static List<string> alllist = new List<string>();   
        static void Main(string[] args)   
        {   
            alllist = f("abcd");   
            foreach (var i in alllist)   
            {   
                Console.WriteLine(i);   
            }   
        }  
 
        static List<string> f(string instring)//遞歸方法的實現   
        {   
            if (instring.Length == 2)//只有當只剩下2個字符的時候，可以返回出結果。   
            {   
                List<string> tmplist = new List<string>();   
                tmplist.Add(instring[0].ToString() + instring[1].ToString());   
                tmplist.Add(instring[1].ToString() + instring[0].ToString());   
                return tmplist;   
            }   
            else   
            {   
                //對于大于2個字符的，只能用+操作來分割計算，也就是combine操作的實現方法分割來計算。   
                return combine(instring[0].ToString(), f(instring.Remove(0, 1)));//把instring的第一個字符分離出來，和后續的字符的全排列做combine操作。返回的是一個集合。   
            }   
        }  
 
        static List<string> combine(string c, List<string> lists)//此處就是上述所說的+操作的實現方法，或者說C操作的實現方法，返回的是一個集合   
        {   
            List<string> output = new List<string>();   
            foreach (string s in lists)   
            {   
                for (int i = 0; i &lt;= s.Length; i++)//c插入到s中的每個位置   
                {   
                    string tmps = "";   
                    tmps = s.Insert(i, c);   
                    output.Add(tmps);   
                }   
            }   
            return output;   
        }   
    }   
}