无recursion函数调用的排列
要求：algorithm生成一个集合的所有可能的组合，不重复，或recursion调用函数返回结果。
大多数，如果不是所有的答案在JavaScript的排列提供？ 从循环或其他函数中recursion调用函数以返回结果。
循环内的recursion函数调用的示例
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()和Array.prototype.reverse()来创build和填充将包含全部六个排列的结果数组。
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());
试图根据在排列和求职面试问题计算 sorting 和求职问题的 C ++实用algorithm中发表的基于图表显示的模式重现结果。
例如，如果input集合是似乎有可能被延伸的模式
["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)); } } } } })
但是尚未能够在上面的js .slice() .concat() .slice()参数上进行必要的调整，以便从一个置换步骤到下一个置换步骤; 而只使用res的前面的数组条目来确定当前的排列，而不使用recursion。
甚至注意到调用的奇数平衡，并尝试使用模%运算符和input数组.length来调用.reverse()或不在["a", "b", "c", "d", "e"]数组，但是没有产生没有重复条目的结果。
预期的结果是，在整个过程期间，上述模式可以被缩减为连续调用的两行，直到所有的排列完成为止。 每个调用.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()来产生给定集合的所有可能的排列，而不用对当前的处理函数进行recursion调用？
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);
编辑，更新
已经find了一个利用上述模式的过程，使用一个for循环，以字典顺序返回到.length 4以下的input的排列。 .length为5数组不返回预期的结果。
该模式基于“计算排列和面试问题” [ 0 ]中的第二个图表。
宁愿不要使用.splice()或.sort()来返回结果，虽然在这里试图坚持最后一个“旋转”的要求在这里使用。 variablesr应该引用下一个排列的第一个元素的index 。
如果使用.splice()的用法遵循图表中的模式，则可以使用.splice() 尽pipe在下面的js ，他们实际上并没有。
不完全确定下面的js问题只是if (i % (total / len) === reset)后面的语句，尽pipe这个部分需要最多的时间投入; 但仍然不会返回预期的结果。
具体来说，现在参考图表，在旋转时，例如2到索引0索引2 。 试图通过使用r （负索引）来实现此目的，从右向左遍历以检索应该位于相邻“列”的index 0处的下一个项目。
在下一列中， 2将被放置在index 2 ， 3将被放置在index 0 。 到目前为止，只要能够掌握或debugging，就是发生错误的部分。
同样，返回[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头部词典：（正式Example_03〜Palindromes）
生成所有的排列[非recursion] （尝试从C++端口到javascript jsfiddle http://jsfiddle.net/tvvvjf3p/ ）
无recursion计算置换 – 第2部分
使用迭代的string排列
迭代置换
置换通过交换
置换algorithm的评估
置换algorithm没有recursion？ Java的
使用重复元素进行全排列的非recursionalgorithm？
Java中的string排列（非recursion）
懒洋洋地产生排列
如何在Python中生成一个列表的所有排列
O（n log n）时间内是否可以生成一个集合或string的所有排列？
寻找“0123456789”的第n个词典排列
组合和排列
这是一个简单的解决scheme来计算string的第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; }
该algorithm遵循以下简单的步骤：
- 首先计算
f = len!，有一系列不同元素的factorial(len)总置换。 - 作为第一个元素，用
(len-1)!分割置换号码(len-1)!并在结果偏移处select元素。 有(len-1)!不同的排列有任何给定的元素作为他们的第一个元素。 - 从集合中删除所选的元素，并使用余数作为置换数继续进行。
- 执行这些步骤与其余的集合，其长度减less一。
这个algorithm非常简单，并且具有有趣的属性：
- 它直接计算第n个排列。
- 如果该集合是有序的，则按字典顺序生成排列。
- 它即使设置元素不能相互比较，如对象，数组，函数…
- 置换数字
0是按给定顺序设置的。 - 排列数
factorial(a.length)-1是最后一个：seta的顺序是相反的。 - 超出此范围的排列将返回未定义状态。
它可以很容易地转换为处理一个存储为数组的集合：
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的其余部分。
我们可以在第二个循环中使用不同的方式，存储除法余数，避免Math.floor()和额外的%运算符。 下面是这个循环的替代scheme，可能更不易读：
// 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; }
创build排列的一种方法是在所有结果中的元素之间的所有空间中添加每个元素。 这可以不使用循环和队列recursion来完成。
JavaScript代码：
function ps(a){ var res = [[]]; for (var i=0; i<a.length; i++){ while(res[res.length-1].length == i){ var l = res.pop(); for (var j=0; j<=l.length; j++){ var copy = l.slice(); copy.splice(j,0,a[i]); res.unshift(copy); } } } return res; } console.log(JSON.stringify(ps(['a','b','c','d'])));
我觉得这个post应该可以帮到你。 该algorithm应该很容易翻译成JavaScript（我认为它已经超过70％已经与JavaScript兼容）。
slice和reverse是不好的电话使用，如果你是后效率。 这篇文章中描述的algorithm遵循next_permutation函数的最有效的实现，甚至集成在一些编程语言中（比如C ++）
编辑
当我再次迭代algorithm时，我认为你可以删除variables的types，并且你应该很好的使用JavaScript。
编辑
JavaScript版本：
function nextPermutation(array) { // Find non-increasing suffix var i = array.length - 1; while (i > 0 && array[i - 1] >= array[i]) i--; if (i <= 0) return false; // Find successor to pivot var j = array.length - 1; while (array[j] <= array[i - 1]) j--; var temp = array[i - 1]; array[i - 1] = array[j]; array[j] = temp; // Reverse suffix j = array.length - 1; while (i < j) { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } return true; }
从Steinhaus-Johnson-Trotteralgorithm得到启发，这可能是另一个解决scheme：
function p(input) { var i, j, k, temp, base, current, outputs = [[input[0]]]; for (i = 1; i < input.length; i++) { current = []; for (j = 0; j < outputs.length; j++) { base = outputs[j]; for (k = 0; k <= base.length; k++) { temp = base.slice(); temp.splice(k, 0, input[i]); current.push(temp); } } outputs = current; } return outputs; } // call var outputs = p(["a", "b", "c", "d"]); for (var i = 0; i < outputs.length; i++) { document.write(JSON.stringify(outputs[i]) + "<br />"); }
这里有一个我自己提出的方法，但自然也能find它在其他地方描述的方法 ：
generatePermutations = function(arr) { if (arr.length < 2) { return arr.slice(); } var factorial = [1]; for (var i = 1; i <= arr.length; i++) { factorial.push(factorial[factorial.length - 1] * i); } var allPerms = []; for (var permNumber = 0; permNumber < factorial[factorial.length - 1]; permNumber++) { var unused = arr.slice(); var nextPerm = []; while (unused.length) { var nextIndex = Math.floor((permNumber % factorial[unused.length]) / factorial[unused.length - 1]); nextPerm.push(unused[nextIndex]); unused.splice(nextIndex, 1); } allPerms.push(nextPerm); } return allPerms; };
Enter comma-separated string (eg a,b,c): <br/> <input id="arrInput" type="text" /> <br/> <button onclick="perms.innerHTML = generatePermutations(arrInput.value.split(',')).join('<br/>')"> Generate permutations </button> <br/> <div id="perms"></div>
我敢添加另一个答案，目的是回答你关于分slice ， concat ， reverse 。
答案是（几乎）可能，但是效果不好。 你在你的algorithm中做什么是以下内容：
- find置换数组中的第一个反转，从右到左（在这种情况下反转定义为
i和j，其中i<j和perm[i]>perm[j]，索引从左到右） - 放置更多的反演
- 按照相反的顺序连接处理的数字，这与已sorting的顺序相同，因为没有观察到反转。
- 连接第二个反演数（仍然按照前面的数字sorting，因为没有观察到反演）
这主要是我的第一个答案，但以一种更优化的方式。
例
考虑置换9,10,11,8,7,6,5,4,3,2,1第一个从右到左的倒置是10,11。而下一个置换实际上是：9,11,1， 2,3,4,5,6,7,8,9,10 = 9concat（11）的concat（REV（8,7,6,5,4,3,2,1））的concat（10）
源代码在这里，我包含了我设想的源代码：
var nextPermutation = function(arr) { for (var i = arr.length - 2; i >= 0; i--) { if (arr[i] < arr[i + 1]) { return arr.slice(0, i).concat([arr[i + 1]]).concat(arr.slice(i + 2).reverse()).concat([arr[i]]); } } // return again the first permutation if calling next permutation on last. return arr.reverse(); } console.log(nextPermutation([9, 10, 11, 8, 7, 6, 5, 4, 3, 2, 1])); console.log(nextPermutation([6, 5, 4, 3, 2, 1])); console.log(nextPermutation([1, 2, 3, 4, 5, 6]));
这里的代码是适合jsfiddle的。
