JavaScript排列

Question

我想計算不包含連續字母的排列數。我的代碼通過測試，如'aabb'（回答：8）和'aab'（回答：2），但不通過像'abcdefa'（我的回答：2520;正確答案：3600）的情況。這是我的代碼：

function permAlone(str) { 

    var totalPerm = 1; 
    var result = []; 

    //assign the first letter 
    for (var i = 0; i < str.length; i++) { 
     var firstNum = str[i]; 
     var perm = firstNum; 

     //create an array from the remaining letters in the string 
     for (var k = 0; k < str.length; k++) { 
      if (k !== i) { 
       perm += str[k]; 
      } 
     } 

     //Permutations: get the last letter and change its position by -1; 
     //Keep changing that letters's position by -1 until its index is 1; 
     //Then, take the last letter again and do the same thing; 
     //Keep doing the same thing until the total num of permutations of the number of items in the string -1 is reached (factorial of the number of items in the string -1 because we already established what the very first letter must be). 

     var permArr = perm.split(""); 
     var j = permArr.length - 1; 
     var patternsLeft = totalNumPatterns(perm.length - 1); 

     while (patternsLeft > 0) { 
      var to = j - 1; 
      var subRes = permArr.move(j, to); 
      console.log(subRes); 

      if (noDoubleLettersPresent(subRes)) { 
       result.push([subRes]); 
      } 

      j -= 1; 
      if (j == 1) { 
       j = perm.length - 1; 
      } 
      patternsLeft--; 
     } 
    } 
    return result.length; 
} 

Array.prototype.move = function(from, to) { 
    this.splice(to, 0, (this.splice(from, 1))[0]); 
    return this.join(""); 
}; 

function totalNumPatterns(numOfRotatingItems) { 
    var iter = 1; 
    for (var q = numOfRotatingItems; q > 1; q--) { 
     iter *= q; 
    } 
    return iter; 
} 

function noDoubleLettersPresent(str) { 
    if (str.match(/(.)\1/g)) { 
     return false; 
    } else { 
     return true; 
    } 
} 

permAlone('abcdefa'); 

Answer 1

我認爲問題是你的置換算法;你從哪裏得到那個的？我用另一個（Filip Nguyen，根據他對this question的回答進行改編）嘗試了它，並按預期返回3600。

function permAlone(str) { 
 
    var result = 0; 
 
    var fact = [1]; 
 
    for (var i = 1; i <= str.length; i++) { 
 
     fact[i] = i * fact[i - 1]; 
 
    } 
 
    for (var i = 0; i < fact[str.length]; i++) { 
 
     var perm = ""; 
 
     var temp = str; 
 
     var code = i; 
 
     for (var pos = str.length; pos > 0; pos--) { 
 
      var sel = code/fact[pos - 1]; 
 
      perm += temp.charAt(sel); 
 
      code = code % fact[pos - 1]; 
 
      temp = temp.substring(0, sel) + temp.substring(sel + 1); 
 
     } 
 
     console.log(perm); 
 
     if (! perm.match(/(.)\1/g)) result++; 
 
    } 
 
    return result; 
 
} 
 

 
alert(permAlone('abcdefa'));

更新：在回答相關的問題，我寫了一個算法不只是蠻力所有的排列，然後跳過相鄰雙打的，但採用的是合乎邏輯的方式只生成正確的排列。這裏解釋這裏：Permutations excluding repeated characters並擴大到包括任何數量的重複每個字符在這裏：Generate all permutations of a list without adjacent equal elements

Answer 2

我同意m69，錯誤似乎是如何生成排列。通過執行不同的生成排列算法，我得到了'abcdefa'的3600。我的解決方案如下。由於它使用遞歸生成排列，所以解決方案並不快，但是如果速度不重要，您可能會發現代碼更容易遵循。

使用單獨的函數在置換中生成數組索引值的原因是爲了驗證置換代碼是否正常工作。由於輸入字符串中存在重複值，因此更難排除排列算法中的問題。

// Simple helper function to compute all permutations of string indices 
function permute_indices_helper(input) { 
    var result = [];  
    if (input.length == 0) { 
     return [[]]; 
    } 
    for(var i = 0; i < input.length; i++) { 
     var head = input.splice(i, 1)[0]; 
     var tails = permute_indices_helper(input); 
     for (var j = 0; j < tails.length; j++) { 
      tails[j].splice(0, 0, head); 
      result.push(tails[j]); 
     } 
     input.splice(i, 0, head); // check 
    } 
    return result; 
}; 

// Given an array length, generate all permutations of possible indices 
// for array of that length. 
// Example: permute_indices(2) generates: 
// [[0,1,2], [0,2,1], [1,0,2], ... , [2, 0, 1]] 
function permute_indices(array_length) { 
    var result = []; 
    for (var i = 0; i < array_length; i++) { 
     result.push(i); 
    } 
    return permute_indices_helper(result); 
} 

// Rearrange letters of input string according to indices. 
// Example: "car", [2, 1, 0] 
// returns: "rac" 
function rearrange_string(str, indices) { 
    var result = ""; 
    for (var i = 0; i < indices.length; i++) { 
     var string_index = indices[i]; 
     result += str[string_index]; 
    } 
    return result; 
} 

function permAlone(str) { 
    var result = 0; 
    var permutation_indices = permute_indices(str.length); 
    for (var i = 0; i < permutation_indices.length; i++) { 
     var permuted_string = rearrange_string(str, permutation_indices[i]); 
     if (! permuted_string.match(/(.)\1/g)) result++; 
    } 
    return result; 
} 

您可以在JSFiddle上看到一個工作示例。