Permutations filtrées sans caractères répétitifs - javascript, filtre, permutation

C'est une tâche de freeCodeCamp.

Mon objectif est de créer une fonction qui:

1. Prend n'importe quelle chaîne avec n'importe quel caractère.
2. Crée un tableau avec toutes les permutations possibles à partir de cette chaîne.
3. Filtre le tableau et renvoie uniquement les chaînes qui n'ont pas de lettres consécutives répétées.

Renvoie le nombre total de permutations duchaîne fournie qui ne comporte pas de lettres consécutives répétées. Supposons que tous les caractères de la chaîne fournie est unique. Par exemple, aab doit renvoyer 2 car il a 6 permutations totales (aab, aab, aba, aba, baa, baa), mais seulement 2 d'entre eux (aba et aba) n'ont pas la même lettre (dans ce cas a) se répéter.

Je ne peux pas comprendre ce que j'ai mal écrit. Je pense que le problème réside soit dans la fonction de filtre, soit dans la liste de permutation est défectueuse.

function permAlone(str) {

if (str.length == 1) {
return str;
}
// Creates all possible Permutations and pushes to an array
var arr = [];
var p = 0; // position of the element which needs to be swapped
// Loop count equal to number of Permutations.
var loops = factorialize(str.length);
for (var i = 0; i < loops; i++) {

// if the position is not the last element in the strig keep swapping with next following character

if (p != str.length - 1) {
var splitStr = str.split("")
arraySwapElements(splitStr, p, p + 1);
str = splitStr.join("");
arr.push(str);
p += 1;
// when position is at the last index, change position to 0
} else {
p = 0;
i -= 1;
}
}

// swaps 2 items in an array

function arraySwapElements(arr, a, b) {
var item = arr[a];
arr[a] = arr[b];
arr[b] = item;
};


// outputs a factorial of a number

function factorialize(num) {
if (num === 0) {
return 1;
} else {
return num * factorialize(num - 1);
}
}

// filters any array which has 2 or more repeating characters

var x = arr.filter(function(str) {
var re = /(.)1+/;
var result = re.test(str);
if (!result) {
return str;
}
})

// returns the filtered arrays length
return x.length



}

console.log(permAlone("abfdefa"));

Lors du test:

permAlone("aab") should return a number. // Correct
permAlone("aab") should return 2.  // Correct
permAlone("aaa") should return 0. // Correct
permAlone("aabb") should return 8. // Correct
permAlone("zzzzzzzz") should return 0.// Correct
permAlone("a") should return 1.// Correct
permAlone("aaab") should return 0.// Correct

permAlone("abcdefa") should return 3600. // Incorrect
permAlone("abfdefa") should return 2640.// Incorrect
permAlone("aaabb") should return 12. // Incorrect

Réponses:

1 pour la réponse № 1

Le problème découle de la logique utilisée dans le for boucle. Bien que la boucle génère le bon nombre de permutations totales, elle ne génère pas toutes les permutations.

Par exemple, si notre chaîne à permuter était "abcd", le mécanisme de permutation générerait des chaînes comme ceci:

bunecd bcuned bcdune

cbda cdbun cdab

récab dacb tamponnerc

unerébc abréc abcré

Oh oh! Ce dernier arrangement est le même que la chaîne de départ. Quand nous recommencerons à swapper, nous "obtiendrons le même ensemble que lors de la première passe. Nous n'obtiendrons jamais une permutation comme" acbd ". Ainsi, le tableau résultant contient des nombres plus élevés de certaines permutations et des nombres inférieurs d'autres.

Je ne sais pas comment le résoudre avec l'approche que vous utilisez, mais une fonction récursive pour obtenir des permutations pourrait être écrite comme ceci:

// Returns an array of all permutations of a string
function getPerms(str) {
// Base case. If the string has only one element, it has only one permutation.
if (str.length == 1) {
return [str];
}
// Initialise array for storing permutations
let permutations = [];
// We want to find the permutations starting with each character of the string
for (let i = 0; i < str.length; i++) {
// Split the string to an array
let splitStr = str.split("");
// Pull out the character we"re checking for permutations starting with
let currentElem = splitStr.splice(i, 1)[0];
// Get permutations of the remaining characters
let subPerms = getPerms(splitStr.join(""));
// Concat each of these permutations with the character we"re checking
// Add them to our list
subPerms.forEach(function (combination) {
permutations.push(currentElem.concat(combination));
});
}
// return our list
return combinations;
}

---