Permutácie filtrované bez opakujúcich sa znakov - javascript, filter, permutácia

Toto je úloha z freeCodeCamp.

Mojím cieľom je vytvoriť funkciu, ktorá:

1. Preberá akýkoľvek reťazec s ľubovoľnými znakmi.
2. Vytvorí pole so všetkými permutáciami z tohto reťazca.
3. Filtruje pole a vracia iba reťazce, ktoré nemajú opakované po sebe idúce písmená.

Vráťte počet celkových permutáciíza predpokladu, že reťazec, ktorý nemá opakované po sebe idúce písmená poskytnuté reťazce sú jedinečné. Napríklad aab by sa mal vrátiť 2 pretože má 6 úplných permutácií (aab, aab, aba, aba, baa, baa), ale len 2 z nich (aba a aba) nemajú rovnaké písmeno (v tomto prípade a) opakovanie.

Môžem "t zistiť, čo som napísal zle. Myslím, že problém spočíva buď vo funkcii filtra alebo permutácia zoznam je chybný."

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

Pri testovaní:

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

odpovede:

1 pre odpoveď č. 1

Problém vychádza z logiky použitej v for slučky. Kým slučka vytvára správny počet celkových permutácií, nevytvára všetky permutácie.

Napríklad, ak bol náš reťazec, ktorý má byť permutovaný, "abcd", mechanizmus výmeny by generoval reťazce takto:

bacd bcad bcda

Cbda cdbcdab

dCab daCb dabC

adbc abdc abcd

Uh Oh! Toto posledné usporiadanie je rovnaké ako štartovací reťazec. Keď znova začneme výmenu, dostaneme tú istú množinu, akú sme urobili na prvom priechode. Nikdy nedostaneme permutáciu ako "acbd". Výsledné pole tak obsahuje vyššie počty niektorých permutácií a nižšie počty ostatných.

"Nie som si istý, ako to opraviť s prístupom, ktorý používate", ale rekurzívna funkcia na získanie permutácií by mohla byť napísaná takto:

// 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;
}

---