无需递归函数调用的排列

要求：算法生成集合的所有可能组合，不重复，或递归调用函数返回结果。

大多数（如果不是全部的话）的答案在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++);

k应该返回6，或可能排列的总数arr ["a", "b", "c"]

确定集合中各个排列的总数后，可以使用以下命令创建和填充包含所有六个排列的结果数组：Array.prototype.slice() , Array.prototype.concat() and 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++ 实用算法中发布的算法 at 计算排列和求职面试问题 .

例如，如果输入集是 ，则似乎存在可以扩展的模式

["a", "b", "c", "d", "e"]

预计有 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确定当前排列，而不使用递归。

注意到调用的偶数、奇数平衡并尝试使用模数%运算符和输入数组.length拨打电话.reverse()或不在["a", "b", "c", "d", "e"]array ，但不会产生没有重复条目的结果。

预期的结果是，上述模式可以减少为在该过程期间连续调用的两行，直到所有排列完成，res填充 ;每人一个，用于拨打.reverse(), 调用无.reverse();例如，之后res[0] filled

// 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);

编辑、更新

已经找到了一个过程，利用上述模式按字典顺序返回输入的排列.length4、使用单for环形。数组不会返回预期结果.length of 5.

The pattern is based on the second chart at "Calculating Permutations and Job Interview Questions"^[0].

宁愿不使用.splice() or .sort()返回结果，尽管在尝试坚持最后一个时使用"rotate"每列的要求。变量r应参考index下一个排列的第一个元素，它确实如此。

指某东西的用途.splice() , .sort()如果它们的使用遵循图表中的模式，则可以包含在内；虽然在js下面，他们实际上没有。

不完全确定问题与js以下仅是以下声明if (i % (total / len) === reset)，尽管这部分需要投入最多的时间；但仍然没有返回预期的结果。

具体来说，现在参考图表，在 旋转 处，例如2索引0, 1索引2。试图通过使用来实现这一点r，这是一个负索引，从右向左遍历以检索应位于的下一个项目index 0相邻的“列”。

在下一栏，2将被放置在index 2 , 3将被放置在index 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 ~ 回文）

生成所有排列[非递归]（尝试从C++ to javascriptjsfiddlehttp://jsfiddle.net/tvvvjf3p/)

不使用递归计算排列 - 第 2 部分

使用迭代对字符串进行排列

迭代排列

通过交换进行排列

排列算法的评估

没有递归的排列算法？爪哇

用于具有重复元素的完全排列的非递归算法？

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

惰性生成排列

如何在Python中生成列表的所有排列

可以在 O(n log n) 时间内生成集合或字符串的所有排列吗？

查找‘0123456789’的第 n 个字典排列

组合和排列

下面是计算字符串第 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!， 有factorial(len)一组的总排列len不同的元素。
• 作为第一个元素，将排列数除以(len-1)!并选择结果偏移处的元素。有(len-1)!以任何给定元素作为第一个元素的不同排列。
• 从集合中删除所选元素并使用除法的余数作为排列数继续进行。
• 与该组的其余部分一起执行这些步骤，其长度减少一。

这个算法非常简单并且具有有趣的特性：

• 它直接计算第 n 次排列。
• 如果集合是有序的，则排列按字典顺序生成。
• 即使集合元素无法相互比较，例如对象、数组、函数......，它也能工作。
• 排列数0是按给定顺序排列的集合。
• 排列数factorial(a.length)-1是最后一个：集合a以相反的顺序。
• 超出此范围的排列将作为未定义返回。

它可以很容易地转换为处理存储为数组的集合：

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首先计算为factorial(len).
• 对于每一步，f除以len，给出精确的前一个阶乘。
• n除以这个新值f给出其中的槽号len具有相同初始元素的槽。 Javascript没有积分除法，我们可以使用(n / f) ... 0)将除法结果转换为其整数部分，但它引入了对 12 个元素的集合的限制。Math.floor(n / f)允许最多包含 18 个元素的集合。我们还可以使用(n - n % f) / f，可能也更有效率。
• n必须减少到该槽内的排列数，即除法的余数n / f.

我们可以使用i在第二个循环中不同的是，存储除法余数，避免Math.floor()和额外的%操作员。这是此循环的替代方案，可能是even可读性较差：

        // 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;
        }