數字全排列

zoomdong 發布于2019-08-15 15:54 / 968人閱讀

摘要：數字全排列問題描述給一個不重復的數字數組，寫一個程序，輸出全排列。那么兩個數字的全排列怎么算呢，以為例，就是第一個數字為的剩下的數的全排列第一個數字為的剩下的數的全排列。依次類推到個數字的全排列設數組，設的全排列為，設。

數字全排列 問題描述

給一個不重復的數字數組，寫一個程序，輸出全排列。

比如給定數組：

[1, 2, 3]

輸出：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

解決思路

這個問題很經典，接下來嘗試使用數學歸納法的思想來解決這個問題。

在中學的時候，我們就知道一個長度為n的數列有n!個排列。因為第一個數字有n種情況，第二個數字有n-1種情況，第三個數字有n-2種情況……第n個數字只有一種情況了，用公式表示就是n*(n-1)*(n-2)….*1 = n!

我們換一個思維來考慮，以數組[1,2,3]為例，它的全排列為：

第一個數字為1的其他兩個數字的全排列 + 第一個數字為2的其他兩個數字的全排列 + 第一個數字為3的其他兩個數字的全排列。

那么兩個數字的全排列怎么算呢，以[1,2]為例，就是：

第一個數字為1的剩下的數的全排列 + 第一個數字為2的剩下的數的全排列。

因為剩下的只有一個數，就不用繼續了，到這就可以輸出了。

依次類推到n個數字的全排列：

設數組 p = {r1, r2, r3, r4, r5…., rn}，設p的全排列為perm(p)，設pn = p - {rn}。

那么perm(p) = { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }。

同樣思路，也可以算出perm(p1), perm(p2), perm(p3)……perm(pn)。

繼續，就可以使用遞歸求解了，遞歸的出口就是perm求的全排列數組里面只有一個值。

代碼實現

下面是java的實現代碼：

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        Test t = new Test();
        t.perm(arr, 0, arr.length);
    }
    
      //求數組全排列
    public void perm(int[] nums, int start, int len) {
        //判斷遞歸出口，當start == len - 1時，也就是要做的全排列只有一個值 ，那么就可以輸出了
        if(start == len - 1) {
            System.out.println(Arrays.toString(nums));
        }else {
            /*
             * 沒有到遞歸出口時，這一段代碼是關鍵
             * for循環模擬的是：
             * { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }
             * 從r1, r2, r3 一直到 rn 作為第一位，求剩下的全排列
             */
            for(int i = start; i < len; i++) {
                swap(nums, start, i);//通過交換，依次將每個數放在第一位
                perm(nums, start + 1, len);//遞歸調用
                swap(nums, start, i);//交換回來，保證原數組不會變，以進行下一輪全排列
            }
        }
    }
    
    //交換數組中的兩個值
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

輸出結果：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

參考：

http://www.cnblogs.com/nokiag...

https://blog.csdn.net/randyji...

云服務器 GPU云服務器字符串全排列 java 全排列數列字符串全排列算法最快的全排列算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/69313.html

[Leetcode] Permutation Sequence 全排列序列

摘要：找規律復雜度時間空間思路由于我們只要得到第個全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據全排列順序的性質，我們可以總結出一個規律假設全排列有個數組成，則第個全排列的第一位是。然后將得到，這個就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 評論0 收藏0
javascript解三階幻方謎題

摘要：謎題三階幻方。試將這個不同整數填入一個的表格，使得每行每列以及每條對角線上的數字之和相同。列出所有的整數填充方案，然后進行過濾。 /* * 謎題--三階幻方。 * 試將1~9這9個不同整數填入一個3×3的表格，使得每行、每列以及每條對角線上的數字之和相同。 * 策略 * 窮舉搜索。列出所有的整數填充方案，然后進行過濾。 * 亮點為遞歸函數getPermut...

Render 2019-08-21 10:24 評論0 收藏0
Python秒算24點，行還是不行？

摘要：周末閑來無事，看到隔壁家的老王在和隔壁家的媳婦玩點，就進屋看了看。發現老王是真不行啊，那不行，這也不行。什么是點我們先來約定下老王和他媳婦玩的點規則給定個任意數字，然后通過，將這個數字計算出。 showImg(https://segmentfault.com/img/remote/1460000019900384?w=472&h=200); 周末閑來無事，看到隔壁家的老王在和隔壁家的媳...

saucxs 2019-07-31 11:31 評論0 收藏0
[Leetcode] Permutations 全排列

摘要：每一輪搜索選擇一個數加入列表中，同時我們還要維護一個全局的布爾數組，來標記哪些元素已經被加入列表了，這樣在下一輪搜索中要跳過這些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...

scq000 2019-08-14 12:31 評論0 收藏0