无需递归函数调用的排列

一尘不染

无需递归函数调用的排列

algorithm

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

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"]);

当前的Question尝试依赖于先前的排列，在线性过程中创建给定的排列。

例如，给定一个数组

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()并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有序排列辞书++算法
在计算排列和面试问题。

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

["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"]，尽管没有重复的条目也不会产生结果。

预期的结果是，在整个过程中，上述模式可以减少到连续调用的两行，直到所有排列完成并res填充为止。每个呼叫一次.reverse()，没有呼叫.reverse();
例如，res[0]装满后

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

编辑，更新

已经找到了一种利用上述模式的方法，可以.length使用单个for循环以字典顺序返回最多4
个输入的排列。预期结果不返回与数组.length的5。

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

尽管在此处尝试遵守每列的最后 “轮换” 要求，但不希望使用.splice()或.sort()不返回结果。该变量应引用下一个排列的第一个元素的。
__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)

阅读 186

2020-07-28

共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!，存在factorial(len)一组len不同元素的总排列。
作为第一个元素，将置换数除以(len-1)!并选择所得偏移量的元素。有(len-1)!任何给定元素作为其第一个元素的不同排列。
从集合中删除选定的元素，并使用除法的其余部分作为排列数继续进行。
与其余的集合一起执行这些步骤，集合的长度减少一。

该算法非常简单，并且具有有趣的属性：

它直接计算第n个排列。
如果集合是有序的，则排列是按字典顺序生成的。
即使set元素不能相互比较，例如对象，数组，函数等，它也可以工作。
排列编号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()和多余的%运算符。下面是该环可以是一种替代甚至
更少可读：

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

2020-07-28