перестановки в Javascript - PullRequest
Новая
       42

перестановки в Javascript

1 голос
/ 02 апреля 2020

Я пытаюсь написать функцию в Javascript, которая может возвращать количество перестановок, а также показывать все перестановки строки (предположим, что не символ повторяется) с использованием рекурсивных методов. Я много видел, используя for l oop, но есть ли способ получить тот же результат без , используя его?

Для количества перестановок, вот моя попытка без использования for l oop

var permutation = function (s) {

    var fac = function (t) {
        if (t === 0) return 1;
        return t*fac(t-1);
    };

    return fac(s.length);
};

Работает хорошо, но я не знаю, как продолжить со списком перестановок. Спасибо за помощь!

Ответы [ 2 ]

1 голос
/ 02 апреля 2020

Эта версия использует довольно простую рекурсию: 

const without = (n) => (xs) => 
  [... xs .slice (0, n), ... xs .slice (n + 1)]

const permutations = (xs) =>
  xs .length == 0
    ? []
  : xs .length == 1
    ? [[xs[0]]]
  : // else
    xs .flatMap ((x, i) => permutations (without (i) (xs)) .map (p => [x, ...p]))

const stringPermutations = (s) => { 
  return permutations (s .split ('')) .map (ss => ss .join (''))
}


console .log (
  stringPermutations ('abcd')
)
.as-console-wrapper {min-height: 100% !important; top: 0}

Существует вспомогательная функция without, которая возвращает копию массива без заданного индекса. Например, without (2) (['a', 'b', 'c', 'd', 'e', 'f']) дает ['a', 'b', 'd', 'e', 'f']. Это используется только один раз внутри нашей основной функции и может быть легко встроено, но мне легче читать как есть.

stringPermutations просто изменяет строку в массив односимвольных строк, вызывает permutations и затем объединяет полученные массивы обратно в строки.

Важная часть - permutations. Он имеет два базовых случая: когда входной массив пуст, он возвращает пустой массив. Когда он имеет только одно значение, он возвращает массив, содержащий массив, содержащий это значение. Во всех других случаях он выбирает каждый элемент по очереди для первого элемента, удаляя его из списка и рекурсивно вызывая permutations с оставшимся списком для последующих позиций.

1 голос
/ 02 апреля 2020

Вот функция для выполнения перестановок в JavaScript без рекурсии. 

function nextPermutation(array, first = 0, last = array.length-1) {
  if(first>=last){
    return false;
  }
  let i = last;
  for(;;){
    const i1 = i;
    if(array[--i]<array[i1]){
      let i2 = last+1;
      while(array[i]>=array[--i2]);
      [array[i], array[i2]] = [array[i2], array[i]];
      reverse(array, i1, last);
      return true;
    }
    if(i===first){
      reverse(array, first, last);
      return false;
    }
  }
}
function reverse(array, i=0, j=array.length-1) {
  while (i < j)
    [array[i++], array[j--]] = [array[j], array[i]];
}

Используйте это так: 

let stra = [..."string"].sort(); // first sort your items in an array

while(nextPermutation(stra)) console.log(stra); // keep going until false

Это можно сделать не-l oop: 

function nextPermutation(array, first = 0, last = array.length-1) {
  if(first>=last){
    return false;
  }
  let i = last;
  function reverse(i, j){
    if(i>=j) return;
    [array[j], array[i]] = [array[i], array[j]];
    reverse(++i, --j);
  }
  return (function _(){
    const i1 = i;
    if(array[--i]<array[i1]){
      let i2 = last+1;
      (function decrement(){
        if(array[i] >= array[--i2]) decrement();
      })();
      [array[i], array[i2]] = [array[i2], array[i]];
      reverse(i1, last);
      return true;
    }
    if(i===first){
      reverse(first, last);
      return false;
    }
    return _();
  })();
}

https://en.cppreference.com/w/cpp/algorithm/next_permutation

...