Рекурсивно печатать все перестановки строки (Javascript)

Я видел версии этого вопроса для других языков, но не для JS.

Можно ли это сделать рекурсивно в одной функции?

Я понимаю, что мне нужно взять первый элемент в строке, а затем добавить его к каждому решению в рекурсию в оставшейся части строки. Так логично, я понимаю, как должна идти рекурсия. Я просто не понимаю, как добавить первый char на каждое из рекурсивных решений

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?
       } 
    }
}

Ответ 1

Давайте напишем функцию, которая возвращает все перестановки строки в виде массива. Поскольку вам не нужны глобальные переменные, возврат перестановок имеет решающее значение.

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

Чтобы распечатать их, просто перейдите по массиву:

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

Надеюсь, что смогу помочь вам в вашем вопросе.

Ответ 2

Проблема перестановок была изучена до смерти. Алгоритм кучи - одно из известных решений. Вот версия в JS, использующая генератор:

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("abcabad".split('')))
.map(perm => perm.join(''))
.filter((el, idx, self) => (self.indexOf(el) === idx)));

Ответ 3

Используйте Рекурсивную функцию, чтобы перебрать строку

    

    function getPermutations(string) {
      var results = [];

      if (string.length === 1) 
      {
        results.push(string);
        return results;
      }

      for (var i = 0; i < string.length; i++) 
      {
        var firstChar = string[i];
        var otherChar = string.substring(0, i) + string.substring(i + 1);
        var otherPermutations = getPermutations(otherChar);
        
        for (var j = 0; j < otherPermutations.length; j++) {
          results.push(firstChar + otherPermutations[j]);
        }
      }
      return results;
    }
    
    var permutation = getPermutations('YES').filter((el, idx, self) => (self.indexOf(el) === idx));
    console.log("Total permutation: "+permutation.length);
    console.log(permutation);

Ответ 4

Полуотключенная тема:

случайная перестановка данной строки так же проста, как rndperm:

i = document.getElementById("word");
b = document.getElementById("butt");

rndperm = (z) => {
  return z.split("").sort(() => ((Math.random() * 3) >> 0) - 1).join("")
}

function scramble() {
  i.value = rndperm(i.value);
}

var z;

function sci() {
  if (z != undefined) {
    clearInterval(z);
    b.innerText = "Scramble";
    z=undefined;
  } else {
    z = setInterval(scramble, 100);
    b.innerText = "Running...";
  }
}

<center><input id="word" value="HelloWorld"></input><button id="butt" onclick=sci()>Scramble</button></center>