字符串的全排列

sunny5541 發布于2019-08-23 11:38 / 2194人閱讀

摘要：問題輸入一個字符串按字典序打印出該字符串中字符的所有排列。如此遞歸處理，從而得到所有字符的全排列。記斐波那契數列的第位這件事為，則有。其中，表示去掉那個開頭字符的剩余字符串的全排列。

問題

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,acb,bac,bca,cab和cba。

地址：https://www.nowcoder.com/prac...

遞歸

思路：從字符串中選出一個字符作為排列的第一個字符，然后對剩余的字符進行全排列。如此遞歸處理，從而得到所有字符的全排列。

分析：我們可以先根據一個實際的例子想想，怎樣才能無遺漏的輸出全排列：

兩個數就不用說了，對于 ab，只有 ab 和 ba 兩種
三個數，比如 abc，我們先分為三種情況，就是 a 開頭，b 開頭和 c 開頭
對于 a 開頭的情況，剩下 b 和 c，這就回到了兩個數的排列；
對于 b 開頭的情況，剩下 a 和 c，這也回到了兩個數的排列；
c 開頭的情況同理；
四個數，先按照開頭分為四種情況，然后按照三個數的排列去處理
……
以此類推

由此可看出，這是一個遞歸。就好像求斐波那契數列的某一個元素，我們要先求出前面的；要想求出前面的，我們就要求出更前面的。記 “斐波那契數列的第 n 位” 這件事為 F(n)，則有 F(n) = F(n - 1) + F(n - 2)。

類似地，記 “求出 n 個字符串的全排列” 這件事為 P(n)，則有 P(n) = 分別以這n個字符之一開頭 + P(n - 1)。其中，P(n - 1) 表示去掉那個開頭字符的剩余字符串的全排列。哪怕只有兩個字符，比如對于上面例子中的 ab，同樣符合這一條結論。

分析：以 "abc" 為例，執行步驟如下：

a 作為開頭 -> 求 bc 全排列 -> 得到 bc 和 cb -> 與 a 合并 -> 得到 abc 和 acb
b 作為開頭 -> 求 ac 全排列 -> 得到 ac 和 ca -> 與 b 合并 -> 得到 bac 和 bca
c 作為開頭 -> 求 ab 全排列 -> 得到 ab 和 ba -> 與 c 合并 -> 得到 cab 和 cba

注：之前遞歸過程選擇的字符，下一次不能再被選。

時間復雜度：O(n！)。

function permutation(str) {
    if(str.length == 0) {
        return [];
    }
    var result = [];
    var sortTemp = "";
    var arr = str.split("");
    // var len = arr.length;
    var result = sortString(arr, sortTemp, result);
    return result;

    function sortString(arr, sortTemp, res) {
        if(arr.length == 0) {
            return res.push(sortTemp);
        } else {
            let isRepeat = {};
            for(let i = 0; i < arr.length; i++) { // 不要用 len
                if(!isRepeat[arr[i]]) {
                    let temp = arr.splice(i, 1)[0]; // i 取出第i個字符作為第一個字符
                    sortTemp += temp;
                    sortString(arr, sortTemp, res); // 固定第一個字符的剩下字符的全排列已完成
                    arr.splice(i, 0, temp); // i 補全 恢復原字符串
                    sortTemp = sortTemp.slice(0, sortTemp.length - 1); // 清空sortTemp: 每次截掉字符串中的最后一個字符
                    isRepeat[temp] = true; // 相同的字符便不再在第一個字符中固定并對剩下的字符進行全排列了
                }
            }    
        }
        return res;
    }
}
permutation("abc")

這里固定字符串數組元素中的第一個字符的方式：是利用數組中splice()方法通過截取出來（刪掉一個元素），完成全排列后再將該字符補全回原字符串中splice()（添加元素）的方式。遍歷該字符串數組，依次截取掉每個字符元素的方式來作為字符串數組元素的第一個字符。

當然還可以通過依次向后交換的方式、或者取出元素以后向后插入的方式、以及經典的回溯法的方式等等。

References

leetcode題解(遞歸和回溯法)
July 算法習題 - 字符串4（全排列和全組合）

云服務器 GPU云服務器最快的全排列算法字符串全排列字符串全排列算法 html網頁的全選

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

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

July 算法習題 - 字符串4（全排列和全組合）

摘要：求字符串的全排列字符串的全排列設計一個算法，輸出一個字符串字符的全排列。的做法沒有結果的，都是在一個字符串上進行的操作。字符串的全組合輸入三個字符，則它們的組合有。因此可以循環字符串長度，然后輸出對應代表的組合即可。求字符串的全排列字符串的全排列設計一個算法，輸出一個字符串字符的全排列。比如，String = abc 輸出是abc,bac,cab,bca,cba,...

tuniutech 2019-08-14 12:11 評論0 收藏0
JS 字符串全排列算法及內存溢出

摘要：問題給定字符串，求出所有由該串內字符組合的全排列。于是我想的辦法是利用尾遞歸優化。算法二尾遞歸終止條件長度為第一次遞歸時，插入首字母遞歸截取了第一個字符的子串函數的第一個參數是本次遞歸的字符串，第二個參數是前個字符的全排列結果。問題給定字符串，求出所有由該串內字符組合的全排列。所包含的字符不重復。輸入：abc 輸出：[abc,acb,bac,bca,cab,cba] 我在實現算法...

sihai 2019-08-22 14:56 評論0 收藏0
如何求ABC的全排列？--如何理解回溯算法？

摘要：它真的是深度優先搜索嗎是真的嗎是真的如果是的話，那它的搜索空間解空間是什么是向量組成的集合，而。既然深度優先搜索剪枝回溯。什么是全排列？從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當m=n時所有的排列情況叫全排列。那么ABC的全排列有哪些？根據定義得到：ABCACBBACBCACABCBA 如何通過程序求解？方法一：暴力...

zero 2019-08-16 16:22 評論0 收藏0
數字全排列

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

zoomdong 2019-08-15 15:54 評論0 收藏0
《劍指offer》分解讓復雜問題更簡單

摘要：拆分鏈表，將和進行拆分，保證原始鏈表不受影響。要求不能創建任何新的結點，只能調整樹中結點指針的指向。輸入一個字符串長度不超過可能有字符重復字符只包括大小寫字母。遞歸，記錄一個當前節點的位置，該位置指向最后一個節點時記錄一次排列。 1.復雜鏈表的復制輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的hea...

wawor4827 2019-08-23 15:27 評論0 收藏0