JavaScript排列 [英] JavaScript Permutations

问题描述

我试图计算不包含连续字母的排列数。我的代码通过测试，如'aabb'（回答：8）和'aab'（回答：2），但不通过像'abcdefa'（我的回答：2520;正确答案：3600）的情况。这里是我的代码：

pre $ function permAlone（str）{

var totalPerm = 1;
var result = [];

//指定第一个字母
（var i = 0; i var firstNum = str [i];
var perm = firstNum;

//从字符串
中剩下的字母中创建一个数组（k = 0; k if（k！= = i）{
perm + = str [k];
}
}

//排列：获取最后一个字母并将其位置更改为-1;
//将这些字母的位置改为-1，直到其索引为1;
//然后，再把最后一个字母做同样的事情;
//继续执行相同的操作，直到达到字符串-1中项目数的排列总数（字符串-1中的项目数量的阶乘-1，因为我们已经建立了第一个字母一定是）。

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 ]）;
返回this.join（）;
};

函数totalNumPatterns（numOfRotatingItems）{
var iter = 1;
for（var q = numOfRotatingItems; q> 1; q--）{
iter * = q;
}
返回iter;


函数noDoubleLettersPresent（str）{
if（str.match（/（。）\1 / g））{
return false;
} else {
return true;
}
}

permAlone（'abcdefa'）;


解决方案

我认为问题是您的置换算法;你从哪里得到那个的？我尝试了一个不同的（在 Filip Nguyen 之后，根据他对），并按预期返回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 ++; 
 
 <返回结果;} alert（permAlone（'abcdefa'））;  

更新：为了回应一个相关的问题，我写了一个算法，它不仅蛮力所有的排列，然后跳过与相邻的双打，但使用一个合乎逻辑的方式来产生正确的排列。这里解释：不包括重复字符的排列，并扩大到包括任何数量的重复每个字符在这里：生成所有的排列组合没有相邻元素的列表

I am trying to count the number of permutations that do not contain consecutive letters. My code passes tests like 'aabb' (answer:8) and 'aab' (answer:2), but does not pass cases like 'abcdefa'(my answer: 2520; correct answer: 3600). Here's my code:

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');

解决方案

I think the problem was your permutation algorithm; where did you get that from? I tried it with a different one (after Filip Nguyen, adapted from his answer to this question) and it returns 3600 as expected.

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'));

UPDATE: In response to a related question, I wrote an algorithm which doesn't just brute force all the permutations and then skips the ones with adjacent doubles, but uses a logical way to only generate the correct permutations. It's explained here: Permutations excluding repeated characters and expanded to include any number of repeats per character here: Generate all permutations of a list without adjacent equal elements

这篇关于JavaScript排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！