Javascript中的排列

Question

我正在尝试使用Javascript编写一个函数，该函数可以返回递归的数目，并且还使用递归方法显示字符串的所有排列（假设重复了非字符）。我已经使用for循环看到了很多东西，但是有没有办法我可以使用它获得相同的结果[[without？

关于排列的数量，这是我不使用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中进行排列的函数。

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

可以设为非循环：
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

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用于后续位置。