Javascript中的排列

Question

我正在尝试用 Javascript 编写一个函数，该函数可以返回排列数，并使用递归方法显示字符串的所有排列（假设没有重复字符）。我已经看到很多使用for循环，但是有没有一种方法可以在不使用它的情况下获得相同的结果？对于排列的数量，这是我不使用for循环的尝试var permutation = function (s) {    var fac = function (t) {        if (t === 0) return 1;        return t*fac(t-1);    };    return fac(s.length);};它运作良好，但我不知道如何继续排列列表。谢谢您的帮助！

Answer 1

这是一个在没有循环的 JavaScript 中进行排列的函数。

像这样使用它：

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

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

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 _();

  })();

}

Answer 2

这个版本使用了一个相当简单的递归：

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']。这仅在我们的 main 函数中使用一次，并且可以轻松内联，但我发现按原样阅读更容易。

stringPermutations只需将字符串更改为单字符字符串数组，调用permutations然后将结果数组连接回字符串。

重要的部分是permutations。它有两种基本情况：当输入数组为空时，它返回一个空数组。当它只有一个值时，它返回一个数组，其中包含一个包含该值的数组。在所有其他情况下，它依次为第一个元素选择每个元素，将其从列表中删除，并permutations使用剩余列表递归调用后续位置。