JS關於字串的全排列演算法及記憶體溢位詳解

本文主要和大家分享JS關於字串的全排列演算法及記憶體溢位詳解，給定字串，求出所有由該字串內字元組合的全排列。所包含的字元不重複。

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

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

演算法一：遞迴

演算法想法：

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

2. #當長度大於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 <p>演算法應該不難理解吧。但當傳參的字串是<code>"abcdefghijkl"</code>時，排列用到的空間是<code>12!=479001600</code>，過大的記憶體佔用導致記憶體溢出。如果你是在自己的PC上執行，那麼可以使用<code>node --max-old-space-size=8192</code>來修改記憶體。但是我需要在Codewars上執行，所以無法修改記憶體。於是我想的辦法是利用尾遞歸優化。呵呵，Node的尾遞歸優化？不管了，先試試吧。 </p><h1 id="演算法二-尾遞歸">演算法二：尾遞歸</h1><pre class="brush:php;toolbar:false">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 <p>函數的第一個參數是本次遞歸的字串，第二個參數是前x個字元的全排列結果。 <br>思路是：</p><ol class=" list-paddingleft-2">
<li><p>每次取當次遞迴串的第一個字母；</p></li>
<li><p>若第二個參數長度為0說明是第一次遞歸，則初始化本次結果為<code>[首字母]</code>。然後將首字母從遞歸串中剔除，剩餘串傳給下一次遞歸;</p></li>
<li><p>#之後每一次遞歸，都取遞歸串的首字母，將其插入前x個字符的全排列的所有位置，求出x+1個字元的全排列；</p></li>
<li>
<p>遞歸直到第一個參數為空串，則第二個參數為字串所有字符的全排列。 </p>
<p>可能不太理解，不過知道這是尾遞歸就行了。雖然尾遞歸在ES6的嚴格模式中才有效，但是，我加上<code>'use strict';</code>後仍然無效。事實上我認為並不是函數呼叫棧的溢出，而是存放變數的堆溢出。所以，大概是無解了吧。畢竟全排列不管怎麼樣，空間複雜度都是O(n!)的。 </p>
</li>
</ol><h1 id="演算法三-循環">演算法三：循環</h1><p>最後再貼個循環的程式碼吧，也是沒什麼用，就當擴充思路了。 </p><pre class="brush:php;toolbar:false">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 <p class="comments-box-content">相關推薦：</p><p class="comments-box-content"><a href="http://www.php.cn/js-tutorial-385800.html" target="_self">JS全排列組合演算法實作方法</a></p><p class="comments-box-content"><a href="http://www.php.cn/js-tutorial-375288.html" target="_self">JavaScript幾種遞歸全排列演算法實例詳解</a> </p><p class="comments-box-content"><a href="http://www.php.cn/js-tutorial-350034.html" target="_self">JavaScript趣題：全排列去重</a></p>#

以上是JS關於字串的全排列演算法及記憶體溢位詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！