Alle Permutationen einer Zeichenfolge rekursiv drucken (Javascript)

Question

Ich habe Versionen dieser Frage für andere Sprachen, aber nicht für JS gesehen.

Ist es möglich, dies rekursiv in einer Funktion zu tun?

Ich verstehe, dass ich das erste Element in der Zeichenfolge und dann an jede Lösung für die Rekursion auf den Rest der Zeichenfolge anhängen müssen. Logischerweise verstehe ich, wie die Rekursion gehen muss. Ich verstehe einfach nicht, wie das erste Zeichen auf jede der rekursiven Lösungen

var myString = "xyz"; 

function printPermut(inputString){ 
    var outputString; 
    if(inputString.length === 0){ 
     return inputString; 
    } 
    if(inputString.length === 1){ 
     return inputString; 
    } 
    else{ 
     for(int i = 0; i<inputString.length(); i++){ 
      //something here like: 
      //outputString = outputString.concat(printPermut(inputString.slice(1))?? 
      //maybe store each unique permutation to an array or something? 
     } 
    } 
} 

Answer 1

anhängen Lassen Sie uns eine Funktion schreiben, die alle Permutationen einer Zeichenkette als ein Array zurückgibt. Da Sie keine globalen Variablen möchten, ist die Rückgabe der Permutationen entscheidend.

function permut(string) { 
    if (string.length < 2) return string; // This is our break condition 

    var permutations = []; // This array will hold our permutations 

    for (var i=0; i<string.length; i++) { 
     var char = string[i]; 

     // Cause we don't want any duplicates: 
     if (string.indexOf(char) != i) // if char was used already 
      continue;   // skip it this time 

     var remainingString = string.slice(0,i) + string.slice(i+1,string.length); //Note: you can concat Strings via '+' in JS 

     for (var subPermutation of permut(remainingString)) 
      permutations.push(char + subPermutation) 

    } 
    return permutations; 
} 

sie zu drucken, nur danach das Array iterieren:

var myString = "xyz"; 
permutations = permut(myString); 
for (permutation of permutations) 
    print(permutation) //Use the output method of your choice 

Hoffe, dass ich Ihnen mit Ihrer Frage helfen könnte.

Answer 2

Das Problem der Permutationen wurde bis zum Tod untersucht. Heap's algorithm ist eine bekannte Lösung. Hier ist eine Version in JS, mit einem Generator:

function *permute(a, n = a.length) { 
 
    if (n <= 1) yield a.slice(); 
 
    else for (let i = 0; i < n; i++) { 
 
    yield *permute(a, n - 1); 
 
    const j = n % 2 ? 0 : i; 
 
    [a[n-1], a[j]] = [a[j], a[n-1]]; 
 
    } 
 
} 
 

 
console.log(Array.from(permute("xyz".split(''))).map(perm => perm.join('')));

permute wurde entwickelt, um Arrays zu nehmen und erzeugen keine Strings, so teilen wir die Zeichenfolge in Zeichen, bevor sie anrufen, und fügen Sie die Zeichen zurück in Strings, bevor Sie die Ergebnisse ausdrucken.