JS 字符串全排列算法及內存溢出

sihai 發布于2019-08-22 14:56 / 672人閱讀

摘要：問題給定字符串，求出所有由該串內字符組合的全排列。于是我想的辦法是利用尾遞歸優化。算法二尾遞歸終止條件長度為第一次遞歸時，插入首字母遞歸截取了第一個字符的子串函數的第一個參數是本次遞歸的字符串，第二個參數是前個字符的全排列結果。

問題

給定字符串，求出所有由該串內字符組合的全排列。所包含的字符不重復。

輸入："abc"
輸出：["abc","acb","bac","bca","cab","cba"]

我在實現算法時遇到了一個問題，至今無法解決。但是全排列算法又很重要，所以寫這篇文章記錄一下。

算法一：遞歸

算法思想：

當字符串長度為1時，輸出該字符串；

當長度大于1時，取字符串的首字母，求出長度-1的串的全排列，將首字母插入每一個排列的任意位置。

算法實現：

function permutate(str) {
    //保存每一輪遞歸的排列結果
    var result = [];
    //初始條件：長度為1
    if (str.length == 1) {
        return [str]
    } else {
        //求剩余子串的全排列,對每個排列進行遍歷
        var preResult = permutate(str.slice(1));
        for (var j = 0; j < preResult.length; j++) {
            for (var k = 0; k < preResult[j].length + 1; k++) {
                //將首字母插入k位置  
                var temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
                result.push(temp);
            }
        }
        return result;
    }
}

算法應該不難理解吧。但是當傳參的字符串是"abcdefghijkl"時，排列用到的空間是12!=479001600，過大的內存占用導致內存溢出。如果你是在自己的PC上執行，那么可以使用node --max-old-space-size=8192來修改內存。但是我需要在Codewars上執行，所以無法修改內存。于是我想的辦法是利用尾遞歸優化。呵呵，Node的尾遞歸優化？不管了，先試試吧。

算法二：尾遞歸

function permutate(str,result) {
    "use strict";
    let tempArr = [];
    //終止條件str長度為0
    if (str.length == 0) {
        return result
    } else {
        //第一次遞歸時，插入首字母
        if(result.length === 0){
            tempArr.push(str[0]);
        }else{
            for (let i = 0; i < result.length; i++) {
                let item = result[i];
                let itemLen = item.length;
                for (let j = 0; j < itemLen+1; j++) {
                    let temp = item.slice(0, j) + str[0] + item.slice(j);
                    tempArr.push(temp);
                }
            }
        }
        //遞歸截取了第一個字符的子串
        return permutate(str.slice(0),tempArr);
    }
}
permutate("abcdefghijkl",[]);

函數的第一個參數是本次遞歸的字符串，第二個參數是前x個字符的全排列結果。
思路是：

每次取當次遞歸串的第一個字母；

若第二個參數長度為0說明是第一次遞歸，則初始化本次結果為[首字母]。然后將首字母從遞歸串中剔除，剩余串傳給下一次遞歸;

之后每一次遞歸，都取遞歸串的首字母，將其插入前x個字符的全排列的所有位置，求出x+1個字符的全排列；

遞歸直到第一個參數為空串，則第二個參數為字符串所有字符的全排列。

可能不太好理解，不過知道這是尾遞歸就行了。雖然尾遞歸在ES6的嚴格模式中才有效，但是，我加上"use strict";后仍然無效。事實上我認為并不是函數調用棧的溢出，而是存放變量的堆溢出。所以，大概是無解了吧。畢竟全排列不管怎么樣，空間復雜度都是O(n!)的。

算法三：循環

最后再貼個循環的代碼吧，也是沒什么用，就當擴展思路了。

function perm(str) {
    let result = [],tempArr = [];
    let subStr = str;
    while (subStr.length !== 0) {
        if (result.length === 0) {
            result.push(str[0]);
        } else {
            for (let i = 0; i < result.length; i++) {
                let item = result[i];
                let itemLen = item.length;
                for (let j = 0; j < itemLen+1; j++) {

                    let temp = item.slice(0, j) + subStr[0] + item.slice(j);
                    tempArr.push(temp);
                }
            }
            result = tempArr;
            tempArr = [];
        }
        subStr = subStr.slice(1);
    }
    return result;
}

總結

第一次遇到解決不了的問題啊，感覺很不開心。我還特地跑到stackoverflow上問了，然后回答的都不能解決。所以我也只好放棄了，真是不甘心。

云服務器 GPU云服務器字符串全排列算法字符串全排列最快的全排列算法字符串轉int算法溢出

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

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

Java 內存結構備忘錄

摘要：本文詳細描述了堆內存模型，垃圾回收算法以及處理內存泄露的最佳方案，并輔之以圖表，希望能對理解內存結構有所幫助。該區域也稱為內存模型的本地區。在中，內存泄露是指對象已不再使用，但垃圾回收未能將他們視做不使用對象予以回收。本文詳細描述了 Java 堆內存模型，垃圾回收算法以及處理內存泄露的最佳方案，并輔之以圖表，希望能對理解 Java 內存結構有所幫助。原文作者 Sumith Puri，...

wow_worktile 2019-08-14 12:50 評論0 收藏0
Javag工程師成神之路（2019正式版）

摘要：結構型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態模式策略模式職責鏈模式責任鏈模式訪問者模式。主要版本更新時間備注 v1.0 2015-08-01 首次發布 v1.1 2018-03-12 增加新技術知識、完善知識體系 v2.0 2019-02-19 結構...

Olivia 2019-08-16 15:14 評論0 收藏0
你和阿里資深架構師之間，差的不僅僅是年齡（進階必看）

摘要：導讀閱讀本文需要有足夠的時間，筆者會由淺到深帶你一步一步了解一個資深架構師所要掌握的各類知識點，你也可以按照文章中所列的知識體系對比自身，對自己進行查漏補缺，覺得本文對你有幫助的話，可以點贊關注一下。目錄一基礎篇二進階篇三高級篇四架構篇五擴導讀：閱讀本文需要有足夠的時間，筆者會由淺到深帶你一步一步了解一個資深架構師所要掌握的各類知識點，你也可以按照文章中所列的知識體系對比自身，對自己...

huaixiaoz 2019-08-15 15:24 評論0 收藏0
java虛擬機

摘要：虛擬機棧線程私有，生命周期跟線程相同。堆用于存放對象實例，是虛擬機所管理的內存中最大的一塊，同時也是所有線程共享的一塊內存區域。統計監測工具語法格式如下是虛擬機，在系統上一般就是進程。 JDK、JRE、JVM三者的關系 JDK(Java Development Kit)是針對Java開發的產品、是整個Java的核心，包括Java運行環境JRE、Java工具包和Java基礎類庫。 JR...

趙春朋 2019-08-16 12:44 評論0 收藏0
JVM 對象引用標記與內存回收算法

摘要：就是說引用計數法很難解決對象之間的相互引用問題也無法通知回收器去及時回收它。因為存在這種缺點，所以現在的虛擬機基本上并不是通過引用計數法來判斷對象是否存活。 1、為什么要進行垃圾回收？每當在我們寫代碼的時候，不管是new一個對象，還是引用，還是填充數據到數組，都是要占用空間，那么如果不及時回收就會對系統的運行產生影響。java和c 一個很大的區別就在于，java的垃圾回收主要是jv...

StonePanda 2019-08-14 17:52 評論0 收藏0