gpt4 book ai didi

JavaScript 排列

转载 作者:行者123 更新时间:2023-11-28 15:20:52 28 4
gpt4 key购买 nike

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

最佳答案

我认为问题出在你的排列算法上;你从哪里得到那个的?我用另一个尝试了它(在 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'));

更新:为了回答一个相关问题,我编写了一个算法,它不仅强制所有排列,然后跳过具有相邻 double 的排列,而且使用逻辑方法仅生成正确的排列。解释如下:Permutations excluding repeated characters并扩展为包括每个字符的任意数量的重复:Generate all permutations of a list without adjacent equal elements

关于JavaScript 排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31505427/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com