Finden Sie die Permutation in Javascript
Harry:
Bei einem Array arraus Größe nund Index 0<=i<n!möchte ich die i-te Permutation zurückgeben.
Ich konnte eine Methode schreiben, die alle Permutationen erhält:
function permute (arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permute(arr.slice(0, i).concat(arr.slice(i + 1)));
for (var j = 0; j < subPerms.length; j++) {
subPerms[j].unshift(arr[i]);
permutations.push(subPerms[j]);
}
}
return permutations;
}
Wie schneide ich es, um nur einen Zweig der Rekursion zu erhalten?
Nina Scholz :
Sie können die Fakultät der Array-Länge als Hilfsmittel zum Abrufen der Zielpermutation verwenden. Grundsätzlich berechnet dieser Algorithmus die Array-Indizes, auf denen das Ergebnis wieder zusammengesetzt wird.
function getN(n, array) {
var f,
l = array.length,
indices = [];
array = array.slice();
while (l--) {
f = factorial(l);
indices.push(Math.floor(n / f));
n %= f;
}
return indices.map(function (i) {
return array.splice(i, 1)[0];
});
}
function factorial(num) {
var result = 1;
while (num) {
result *= num;
num--;
}
return result;
}
var i, l,
array = [1, 2, 3, 4];
for (i = 0, l = factorial(array.length); i < l; i++) {
console.log(i, '>', getN(i, array).join(' '));
}.as-console-wrapper { max-height: 100% !important; top: 0; }