Получить перестановки слов

Question

Я хочу написать функцию для получения всех перестановок элементов массива.

Я не хочу, чтобы вы написали эту функцию для меня! Я хочу проработать это сам. Пожалуйста, сделайте мне одолжение, дайте мне поработать над этим.

Входные данные : [1,2,3] Выходные данные : 123, 132, 213, 231, 312, 321.

Я считаю, что выходные данные должны быть массивом факториала длины (input.length) , Поэтому, если вход представляет собой массив из трех элементов, вывод должен содержать 3 * 2 элемента. В результате ввода четырехэлементного массива длина массива составит 24 (4 * 3 * 2) элемента, причем каждый элемент входного массива является первым элементом массива из шести элементов.

Input : ['a', 'bo'] Выход : ['abo', 'boa']

Вход : [1,2,3,4] Выход :

[
1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321
]

(запятые в выходном псевдокоде опущены).

Вот то, что я имею до сих пор. Это не работает Я думаю, что мне нужен вложенный l oop.

function getWordPermutations(words) {
    const len = words.length;
    const factorial = n => !(n > 1) ? 1 : factorial(n - 1) * n;
    let r = [words.join("")];

    for(let i = 0; i < words.length; i++) {
        let tmp = words[i];
        let nextIndex = words[i+1] ? i+1 : words.length-1 - i;
        words[i] = words[nextIndex];
        words[nextIndex] = tmp;
        r.push(words.join(""))
    }
    console.log(r);
    return r;
}

getWordPermutations([1,2,3]); // Result: ["123", "213", "231", "132"]

Он не завершает все перестановки. Можете ли вы задать мне несколько вопросов, чтобы заставить меня подумать об этом.

Answer 1

Взят от, https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/StringPermutation.java

и повторно реализовано в Javascript.

function permute(input) {
  let countMap = new Map();
  for (ch of input.split("")) {
    //console.log(ch, countMap.has(ch));
    if (countMap.has(ch)) {
      let inc = countMap.get(ch) + 1;
      countMap.set(ch, inc);
    } else {
      countMap.set(ch, 1);
    }
  }
  //console.log(countMap);
  str = new Array(countMap.size); //char[countMap.size()];
  count = new Array(countMap.size); //int[countMap.size];
  index = 0;
  for (let [key, val] of countMap.entries()) {
    //console.log(key, val);
    str[index] = key;
    count[index] = val;
    index++;
  }
  //console.log(str, count);
  resultList = new Array();
  result = new Array(input.length); //char[input.length]
  permuteUtil(str, count, result, 0, resultList);
  return resultList;
}

function permuteUtil(str, count, result, level, resultList) {
  if (level == result.length) {
    resultList.push(result.join("")); //resultList.add(new String(result));
    return;
  }

  for (let i = 0; i < str.length; i++) {
    if (count[i] == 0) {
      continue;
    }
    result[level] = str[i];
    count[i]--;
    permuteUtil(str, count, result, level + 1, resultList);
    count[i]++;
  }
}

permute("AABC").forEach((s) => console.log(s));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Выход соответствует ожидаемому:

AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA

Если вы хотите динамический c ввод и вывод через HTML и разрешить использовать не только отдельные символы (https://codepen.io/Alexander9111/pen/abOMpgz) :

Для ваших конкретных c примеров нам просто нужно ввести список через запятую, например «1,2,3» во входной тег HTML:

function permute(input) {
  let countMap = new Map();
  const input_arr = input.split(",");
  for (ch of input_arr) {
    //console.log(ch, countMap.has(ch));
    if (countMap.has(ch)) {
      let inc = countMap.get(ch) + 1;
      countMap.set(ch, inc);
    } else {
      countMap.set(ch, 1);
    }
  }
  //console.log(countMap);
  str = new Array(countMap.size); //char[countMap.size()];
  count = new Array(countMap.size); //int[countMap.size];
  index = 0;
  for (let [key, val] of countMap.entries()) {
    //console.log(key, val);
    str[index] = key;
    count[index] = val;
    index++;
  }
  //console.log(str, count);
  resultList = new Array();
  result = new Array(input_arr.length); //char[input.length]
  permuteUtil(str, count, result, 0, resultList);
  return resultList;
}

function permuteUtil(str, count, result, level, resultList) {
  if (level == result.length) {
    resultList.push(result.join(',')); //resultList.add(new String(result));
    return;
  }

  for (let i = 0; i < str.length; i++) {
    if (count[i] == 0) {
      continue;
    }
    result[level] = str[i];
    count[i]--;
    permuteUtil(str, count, result, level + 1, resultList);
    count[i]++;
  }
}

//permute("1,2,3").forEach((s) => console.log(s));
const output_tag = document.getElementById("output");
const input_tag = document.getElementById("input");
const go = document.getElementById("go");
go.addEventListener("click", (e) => {
  output_tag.innerText = permute(String(input_tag.value)).join("\n");
});
output_tag.innerText = permute(String(input_tag.value)).join("\n");

<h3>Input (comma separated):</h3>
<input id="input" value="1,2,3">
<br /><br />
<button id="go">Go</button>
<br>
<h3>Output:</h3>
<div id="output"></div>