JavaScript排列_JavaScript

我正在尝试计算不包含连续字母的排列数。 我的代码通过了“ 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');

我认为问题在于您的置换算法； 你从哪里得到那个的？ 我尝试了另一种方法（在，根据他对回答改编了），结果返回了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'));

更新：针对一个相关的问题，我编写了一种算法，该算法不仅对所有排列进行暴力破解，然后跳过具有相邻双精度数的排列，但使用一种逻辑方法仅生成正确的排列。 在此进行说明：并在此处扩展为包括每个字符任何数目的重复：

我同意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;
}

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

JavaScript排列

问题描述

1楼

2楼