无递归函数调用的置换

Question

需求：生成一个集合的所有可能组合的算法，没有重复项，或者递归调用函数返回结果。

在JavaScript中排列提供的大部分答案，如果不是全部的话？从循环或其他函数中递归调用函数以返回结果。

循环内递归函数调用示例

function p(a, b, res) {
  var b = b || [], res = res || [], len = a.length;
  if (!len) 
    res.push(b)
  else 
    for (var i = 0; i < len 
         // recursive call to `p` here
       ; p(a.slice(0, i).concat(a.slice(i + 1, len)), b.concat(a[i]), res)
       , i++
    );
  return res
}

p(["a", "b", "c"]);

var arr = ["a", "b", "c"];

for (var len = 1, i = k = arr.length; len < i ; k *= len++);

在为一个集合确定了各个置换的总数之后，可以使用array.prototype.slice()、array.prototype.concat()和array.prototype.reverse()创建并填充包含所有六个置换的结果数组

var res = new Array(new Array(k));

res[0] = arr;

res[1] = res[0].slice(0,1).concat(res[0].slice(-2).reverse());

res[2] = res[1].slice(-1).concat(res[1].slice(0,2));

res[3] = res[2].slice(0,1).concat(res[2].slice(-2).reverse());

res[4] = res[3].slice(-2).concat(res[3].slice(0,1));

res[5] = res[4].slice(0,1).concat(res[4].slice(-2).reverse());

在计算排列和工作面试问题时，试图根据图中显示的模式再现有序词典排列算法的结果，该算法是基于C++实用算法中发表的一个算法。

如果输入集是

其中需要120个排列。

一个仅依靠前一次置换来填充数组的尝试示例

// returns duplicate entries at `j`
var arr = ["a", "b", "c", "d", "e"], j = [];
var i = k = arr.length;
arr.forEach(function(a, b, array) {
 if (b > 1) {
  k *= b;
  if (b === i -1) {
    for (var q = 0;j.length < k;q++) {
      if (q === 0) {
       j[q] = array;
      } else {
       j[q] = !(q % i) 
              ? array.slice(q % i).reverse().concat(array.slice(0, q % i)) 
              : array.slice(q % i).concat(array.slice(0, q % i));
      }
    }
  }
 }
})

但是，还不能对.slice()、.concat()、.reverse()以上JS的参数进行必要的调整，以便从一个置换步进到下一个置换；而仅使用res中的前一个数组项来确定当前排列，而不使用递归。

// odd , how to adjust `.slice()` , `.concat()` parameters 
// for array of unknown `n` `.length` ?
res[i] = res[i - 1].slice(0,1).concat(res[i - 1].slice(-2).reverse());
// even    
res[i] = res[1 - 1].slice(-1).concat(res[i - 1].slice(0,2));

问题：对上述模式的哪些调整是必要的，特别是参数或索引，传递.slice()，.concat()，以便在不使用对当前处理函数的递归调用的情况下产生给定集合的所有可能的排列？

var arr = ["a", "b", "c"];

for (var len = 1, i = k = arr.length; len < i; k *= len++);

var res = new Array(new Array(k));

res[0] = arr;

res[1] = res[0].slice(0, 1).concat(res[0].slice(-2).reverse());

res[2] = res[1].slice(-1).concat(res[1].slice(0, 2));

res[3] = res[2].slice(0, 1).concat(res[2].slice(-2).reverse());

res[4] = res[3].slice(-2).concat(res[3].slice(0, 1));

res[5] = res[4].slice(0, 1).concat(res[4].slice(-2).reverse());

console.log(res);

编辑，更新

已经找到了一个进程，可以利用上面描述的模式，使用一个for循环，以词典顺序返回.length4以下的输入排列。对于.length为5的数组，未返回预期结果。

该模式基于“计算排列和工作面试问题”^[0]中的第二个图表。

我不喜欢使用.splice()或.sort()返回结果，但在这里使用时，试图遵守每列的最后一个“旋转”要求。变量R应该引用下一个置换的第一个元素的索引。

如果.splice()、.sort()的用法遵循图表中的模式，则可以包括.splice()的用法；尽管在下面的js中，它们实际上没有。

具体地说，现在参考图表，在旋转时，例如2到索引0，1到索引2。试图通过使用R（它是一个负索引）从右向左遍历来检索下一个应该位于相邻“列”的索引0的项来实现这一点。

在下一列中，2将放在索引2，3将放在索引0。这是迄今为止所能掌握或调试的部分，是发生错误的区域。

同样，返回[1,2,3,4]的预期结果，但不返回[1,2,3,4,5]的预期结果

var arr = [1, 2, 3, 4];
for (var l = 1, j = total = arr.length; l < j ; total *= l++);
for (var i = 1
     , reset = 0
     , idx = 0
     , r = 0
     , len = arr.length
     , res = [arr]
     ; i < total; i++) {
  // previous permutation
  var prev = res[i - 1];
  // if we are at permutation `6` here, or, completion of all 
  // permutations beginning with `1`;
  // setting next "column", place `2` at `index` 0;
  // following all permutations beginning with `2`, place `3` at
  // `index` `0`; with same process for `3` to `4`
  if (i % (total / len) === reset) {
    r = --r % -(len);
    var next = prev.slice(r);
    if (r === -1) {
      // first implementation used for setting item at index `-1`
      // to `index` 0
      // would prefer to use single process for all "rotations",
      // instead of splitting into `if` , `else`, though not there, yet
      res[i] = [next[0]].concat(prev.slice(0, 1), prev.slice(1, len - 1)
               .reverse());
    } else {
      // workaround for "rotation" at from `index` `r` to `index` `0`
      // the chart does not actually use the previous permutation here,
      // but rather, the first permutation of that particular "column";
      // here, using `r` `,i`, `len`, would be 
      // `res[i - (i - 1) % (total / len)]`
      var curr = prev.slice();
      // this may be useful, to retrieve `r`, 
      // `prev` without item at `r` `index`
      curr.splice(prev.indexOf(next[0]), 1);
      // this is not optiomal
      curr.sort(function(a, b) {
        return arr.indexOf(a) > arr.indexOf(b)
      });
      // place `next[0]` at `index` `0`
      // place remainder of sorted array at `index` `1` - n
      curr.splice(0, 0, next[0])
      res[i] = curr
    }
    idx = reset;
  } else {
    if (i % 2) {
      // odd
      res[i] = prev.slice(0, len - 2).concat(prev.slice(-2)
              .reverse())
    } else {
      //  even
      --idx
      res[i] = prev.slice(0, len - (len - 1))
               .concat(prev.slice(idx), prev.slice(1, len + (idx)))
    }
  }
}
// try with `arr` : `[1,2,3,4,5]` to return `res` that is not correct;
// how can above `js` be adjusted to return correct results for `[1,2,3,4,5]` ?
console.log(res, res.length)

资源：

用Javascript生成置换

（倒计时）QuickPerm头词典编纂：（正式示例_03~回文）

无递归置换算法？爪哇

具有重复元素的全置换的非递归算法？

Java中的字符串排列（非递归）

Answer 1

下面是一个计算字符串第n次排列的简单解决方案：

function string_nth_permutation(str, n) {
    var len = str.length, i, f, res;

    for (f = i = 1; i <= len; i++)
        f *= i;

    if (n >= 0 && n < f) {
        for (res = ""; len > 0; len--) {
            f /= len;
            i = Math.floor(n / f);
            n %= f;
            res += str.charAt(i);
            str = str.substring(0, i) + str.substring(i + 1);
        }
    }
    return res;
}

该算法遵循以下简单步骤：

• 首先计算f=len！，有f=len！一组len不同元素的阶乘(len)总排列。
• 作为第一个元素，将置换数除以(len-1)！并选择产生偏移量的元素。有(len-1)！不同的排列，它们的第一个元素都是给定的元素。
• 从集合中删除选定的元素，并使用除法的剩余部分作为排列数继续进行。
• 对集合的其余部分执行这些步骤，这些部分的长度减少了1。

null

function array_nth_permutation(a, n) {
    var b = a.slice();  // copy of the set
    var len = a.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}

澄清：

• F首先作为阶乘(len)计算。
• 对于每一步，f除以len，给出了前一个阶乘。
• n除以f这个新值，给出具有相同初始元素的len插槽中的插槽号。Javascript没有整数除法，我们可以使用(n/f)...0)将除法的结果转换为整数部分，但它限制了12个元素的集合。Math.flail(n/f)允许最多18个元素的集合。我们也可以使用(n-n%f)/f，这可能也更有效。
• n必须还原为此槽中的置换数，即n/f除法的余数。

在第二个循环中，我们可以不同地使用i，存储除余数，避免使用Math.floel()和额外的%运算符。下面是这个循环的一个替代方案，它的可读性可能更差：

        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            i = n % (f /= len);
            res.push(b.splice((n - i) / f, 1)[0]);
            n = i;
        }