100 個數，如何遍歷得到所有全排列？

01-26

其中 [1, 2, 3] 和 [2, 3, 1] 是不同的排列。

如果1-100都需要選擇的話，可以利用字典序法變形一下。

參閱Python的庫函數permutation.

9.7. itertools

或者參見How to generate all permutations of a list in Python

這麼龐大的數字，不建議用遞歸演算法，無論是時間還是空間，遞歸演算法都會佔用比非遞歸演算法更多的資源。非遞歸演算法推薦@曹鵬的方法，但後面（i + 1）到結尾的處理不是直接翻轉，而是要做一個排序，因為（i + 1）本身不一定是最大的。但由於它後面的序列是有序的，這個排序只需要 O(n) 的複雜度。

總數是在100的階乘吧。。100！，有多少了？？

比較適合討論演算法，但是幾乎難以實現輸出

對於這個問題，可以按照下面的方法慢慢分析

第 1 步：

當只有1個數字1的時候，只有一種組合

第 2 步：

當有兩個數字1、2的時候，分別把 2 放到 1 的前面和後面，就可以得到下面兩個組合

第 3 步.

當有三個數字1、2、3的時候，可以針對第 2 步中得到的兩個組合，把 3 分別插入這兩個組合之中。

對於組合 2 1，我們可以得到下面 3 個組合：

3 2 1
2 3 1
2 1 3

對於組合 1 2，我們可以得到下面 3 個組合：

3 1 2
1 3 2
1 2 3

於是我們一共得到了 6 個組合

第 4 步：

對於四個數字1、2、3、4，按照第 3 步中的做法，將 4 分別插入在第 3 步中得到的 6 個組合，最後我們可以得到 24 個組合

依此類推，直到100個數字的情況

這樣類推之後，就可以很輕鬆地寫一個遞歸函數來實現

定義一個全局數組，把100個數放進去，然後寫一個迭代函數，從數組裡依次取一個數出來然後進入下一個迭代並繼續從剩下的數里取一個出來，直到數組裡的數被取空，輸出結果；然後回到上一層迭代繼續取沒有取過的數。

-- | The permutations function returns the list of all permutations of the argument. -- -- &> permutations "abc" == ["abc","bac","cba","bca","cab","acb"] permutations :: [a] -&> [[a]] permutations xs0 = xs0 : perms xs0 [] where perms [] _ = [] perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is) where interleave xs r = let (_,zs) = interleave id xs r in zs interleave _ [] r = (ts, r) interleave f (y:ys) r = let (us,zs) = interleave (f . (y:)) ys r in (y:us, f (t:y:us) : zs)

100！的數量級十分龐大，其實計算一串數字的全排列可以用遞歸的方式解決。

比如 1，2，3 這個序列

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

是這六個，確定了第一位之後，後兩位的排列也是如此的（遞歸）

所以先解決 1 X X的排列再解決 2 X X 的排列最後解決 3 X X的排列。

解決 X X 也可以看作是解決一個 2 個數字的排列，於是這就是遞歸的部分了。每次拿一個數字到最前面，剩餘的 n-1(n是序列長度)的進行遞歸的全排列，就得到了最後的結果。

網上有很多代碼，搜一搜就有了。

100個數全排列太多了。全排列的做法有遞歸的和非遞歸的，非遞歸的就是數學方法：找到最後一個a[i]&

組合遍歷使用遞歸代碼會變得簡潔很多

使用兩種方法實現遍歷,第一種使用 @宋良駿的思路實現遍歷 "ABC" ,

// C# namespace PermutationsCalculator { using System;


    public class Permute3

    {

        public static void Go(string prefix, string suffix)

        {

            if (string.IsNullOrWhiteSpace(suffix))

            {

                return;

            }

            if (suffix.Length == 1)  //最後一個字元

            {

                Console.WriteLine(prefix + suffix); // 處理:輸出

            }

// 轉化為數組 var charArr = suffix.ToCharArray(); for (int i = 0; i &< charArr.Length; i++) { var tmpPrefix = prefix + charArr[i]; // 添加當前字元 var tmpSuffix = suffix.Remove(i, 1); // 移除當前字元 Go(tmpPrefix, tmpSuffix); // 繼續執行 } } static void Main(string[] args) { Permute3.Go(string.Empty, "ABC"); } } } 輸出: ABC ACB BAC BCA CAB CBA

通過遞歸執行過程,比較容易理解遞歸2 | shzy2012

使用交換方式實現

// C# namespace PermutationsCalculator { using System; using System.Collections.Generic;


    public class Permute4

    {

        /// &
        /// 交換

        /// &
        /// &
&
        /// &
&
        public static void swap(ref char a, ref char b)

        {

            if (a == b) return;

            var tmp = a;

            a = b;

            b = tmp;

        }

public static void Go(char[] charList, int index) { if (index == charList.Length) //結束條件 { Console.Write(charList); //處理: 輸出 Console.WriteLine(string.Empty);//換行 return; } int i; for (i = index; i &< charList.Length; i++) { swap(ref charList[index], ref charList[i]); Go(charList, index + 1); swap(ref charList[index], ref charList[i]); } } static void Main(string[] args) { Permute4.Go("ABC".ToCharArray(), 0); } } } 輸出: ABC ACB BAC BCA CAB CBA

執行過程遞歸3 | shzy2012

100!=9.3326215443944152681699238856267e+157

lua代碼實現如下：

t={1,2,3}

function permutation(t,n)

if n==1 then

printT(t)

end

for i=1,n do

t[i],t[n]=t[n],t[i]

permutation(t,n-1)

t[i],t[n]=t[n],t[i]

end

function printT(t)

for k,v in pairs(t) do

io.write(v," ")

end

io.write("
")

end

permutation(t,#t)

每次先確定最後一位，然後遞歸。

使用@greensea 的思路，用JS實現

/** * @param {number[]} nums * @return {number[][]} */ var permute = function(nums) { var ret = []; if(nums.length == 1) { ret.push(nums); return ret; }


    var item, item_copy;

    var head = nums.shift();

    var pre_ret = permute(nums);

for(var i = 0; i &< pre_ret.length; i++ ) { item = pre_ret[i]; for(var j = 0; j &<= item.length; j++) { item_copy = [].slice.call(item); item_copy.splice(j, 0, head); ret.push(item_copy); } } return ret; };

我這段代碼可以實現字典序輸出。

#include &

#include&

using namespace std;

void swap(char a,char b){

char temp = a;

a = b;

b = temp;

}

void perm(char a[], int i, int n)

{

int j;

if (i==n-1)

{

for (j = 0; j &< n; j++)

{

cout &<&< a[j];

}

cout &<&< endl;

}

else {

for (j = i; j &< n; j++)

{

sort(a + i , a + strlen(a));

swap(a[j], a[i]);

perm(a, i + 1, n);

swap(a[j], a[i]);

}

int main()

{

char a[10];

cin &>&> a;

perm(a, 0, strlen(a));

system("pause");

return 0;

}

100!≈9×10∧157

可以輸出，存儲是災難。

可以用遞歸實現把工作都丟給電腦，遞歸也沒接觸的話還是先學習一下這種方法吧，也可以用數學的排列組合想出比較優秀的演算法快速解決。