没有递归函数调用的排列
Permutations without recursive function call
要求：生成集合所有可能组合的算法，不重复，或递归调用函数以得到 return 结果。
Permutations in JavaScript? 中提供的大多数（如果不是全部）答案都是从循环或其他函数中递归调用函数以得到 return 结果。
循环内递归函数调用示例[=90=]
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 应该 return 6 ，或者 arr ["a", "b", "c"]
的可能排列总数
根据为集合确定的单个排列的总数，可以使用 Array.prototype.slice() 、Array.prototype.concat() 和 Array.prototype.reverse()[ 创建并填充包含所有六个排列的结果数组=90=]
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++ 实用算法 Calculating Permutations and Job Interview Questions 中发表的算法。
如果输入集是 ，似乎有一个可以扩展的模式，例如
["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 filled ;每个调用 .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);
编辑、更新
找到了一个过程，使用单个 for 循环，将上述模式用于 return 字典顺序的排列，最多为 .length 4 的输入。对于 .length of 5 的数组，预期结果未 returned。
该形态基于 "Calculating Permutations and Job Interview Questions"[0].[=90 处的第二张图表=]
不希望使用 .splice() 或 .sort() 到 return 结果，尽管在此处使用时试图遵守最后的 "rotate" 每列的要求。变量 r 应该引用下一个排列的第一个元素的 index，它确实如此。
如果.splice()、.sort()的用法遵循图表中的模式，则可以包括在内；尽管在 js 下面，他们实际上没有。
不完全确定下面 js 的问题只是 if (i % (total / len) === reset) 之后的语句，尽管这部分需要投入最多的时间；但仍然没有 return 预期结果。
具体来说，现在参考图表，在旋转时，例如 2 到索引 0，1 到索引 2。尝试通过使用负索引 r 从右向左遍历以检索应位于相邻 index 0 的下一个项目来实现此目的 "column" .
在下一列中，2 将放置在 index 2 处，3 将放置在 index 0 处。这是部分，就目前为止能够掌握或调试的，是出错的地方。
同样，return[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)
资源：
Generating Permutation with Javascript
(倒计时)快烫头词典编纂：
(正式Example_03~回文)
Generating all Permutations [non-recursive]
（尝试从 C++ 移植到 javascript jsfiddle http://jsfiddle.net/tvvvjf3p/）
Calculating Permutation without Recursion - Part 2
permutations of a string using iteration
Evaluation of permutation algorithms
Permutation algorithm without recursion? Java
Non-recursive algorithm for full permutation with repetitive elements?
String permutations in Java (non-recursive)
Generating permutations lazily
How to generate all permutations of a list in Python
Can all permutations of a set or string be generated in O(n log n) time?
我认为这个 post 应该对您有所帮助。该算法应该很容易翻译成 JavaScript（我认为它已经超过 70% JavaScript 兼容）。
如果您追求效率，slice 和 reverse 是不好的调用。 post 中描述的算法遵循 next_permutation 函数的最有效实现，甚至集成在某些编程语言中（例如 C++）
编辑
当我再次迭代算法时，我认为你可以只删除变量的类型，你应该很好地进入 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;
}
这是我自己想出的一种方法的片段，但自然也能找到它 described elsewhere:
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 (e.g. 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>
说明
由于给定数组 arr 有 factorial(arr.length) 个排列，0 和 factorial(arr.length)-1 之间的每个数字都编码一个特定的排列。要取消对排列数的编码，请重复从 arr 中删除元素，直到没有元素为止。要删除的元素的确切索引由公式 (permNumber % factorial(arr.length)) / factorial(arr.length-1) 给出。可以使用其他公式来确定要删除的索引，只要它保留数字和排列之间的一对一映射即可。
例子
以下是如何为数组 (a,b,c,d) 生成所有排列：
# Perm 1st El 2nd El 3rd El 4th El
0 abcd (a,b,c,d)[0] (b,c,d)[0] (c,d)[0] (d)[0]
1 abdc (a,b,c,d)[0] (b,c,d)[0] (c,d)[1] (c)[0]
2 acbd (a,b,c,d)[0] (b,c,d)[1] (b,d)[0] (d)[0]
3 acdb (a,b,c,d)[0] (b,c,d)[1] (b,d)[1] (b)[0]
4 adbc (a,b,c,d)[0] (b,c,d)[2] (b,c)[0] (c)[0]
5 adcb (a,b,c,d)[0] (b,c,d)[2] (b,c)[1] (b)[0]
6 bacd (a,b,c,d)[1] (a,c,d)[0] (c,d)[0] (d)[0]
7 badc (a,b,c,d)[1] (a,c,d)[0] (c,d)[1] (c)[0]
8 bcad (a,b,c,d)[1] (a,c,d)[1] (a,d)[0] (d)[0]
9 bcda (a,b,c,d)[1] (a,c,d)[1] (a,d)[1] (a)[0]
10 bdac (a,b,c,d)[1] (a,c,d)[2] (a,c)[0] (c)[0]
11 bdca (a,b,c,d)[1] (a,c,d)[2] (a,c)[1] (a)[0]
12 cabd (a,b,c,d)[2] (a,b,d)[0] (b,d)[0] (d)[0]
13 cadb (a,b,c,d)[2] (a,b,d)[0] (b,d)[1] (b)[0]
14 cbad (a,b,c,d)[2] (a,b,d)[1] (a,d)[0] (d)[0]
15 cbda (a,b,c,d)[2] (a,b,d)[1] (a,d)[1] (a)[0]
16 cdab (a,b,c,d)[2] (a,b,d)[2] (a,b)[0] (b)[0]
17 cdba (a,b,c,d)[2] (a,b,d)[2] (a,b)[1] (a)[0]
18 dabc (a,b,c,d)[3] (a,b,c)[0] (b,c)[0] (c)[0]
19 dacb (a,b,c,d)[3] (a,b,c)[0] (b,c)[1] (b)[0]
20 dbac (a,b,c,d)[3] (a,b,c)[1] (a,c)[0] (c)[0]
21 dbca (a,b,c,d)[3] (a,b,c)[1] (a,c)[1] (a)[0]
22 dcab (a,b,c,d)[3] (a,b,c)[2] (a,b)[0] (b)[0]
23 dcba (a,b,c,d)[3] (a,b,c)[2] (a,b)[1] (a)[0]
请注意，每个排列 # 的形式为：
(firstElIndex * 3!) + (secondElIndex * 2!) + (thirdElIndex * 1!) + (fourthElIndex * 0!)
基本上就是解释中给出的公式的逆过程
创建排列的一种方法是将每个元素添加到目前所有结果中元素之间的所有空格中。这可以在没有递归的情况下使用循环和队列来完成。
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'])));
这可能是另一个解决方案，灵感来自 Steinhaus-Johnson-Trotter algorithm:
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 />");
}
我敢再补充一个答案，旨在回答你关于slice、concat、reverse的问题。
答案是可以（几乎），但效果不会太好。您在算法中所做的如下：
- 从右到左查找排列数组中的第一个反转（本例中的反转定义为
i and j where i < j and perm[i] > perm[j]，索引从左到右）
- 放置倒数较大的数
- 以相反的顺序连接处理过的数字，这将与排序顺序相同，因为没有观察到倒置。
- 连接反转的第二个数字（仍然按照前面的数字排序，因为没有观察到反转）
这主要是我的第一个答案所做的，但以更优化的方式进行。
例子
考虑排列 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 here。
这是计算字符串第 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!，一组 len 个不同元素共有 factorial(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;
}
没有递归的相当简单的 C++ 代码。
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
// Integer data
void print_all_permutations(std::vector<int> &data) {
std::stable_sort(std::begin(data), std::end(data));
do {
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")), std::cout << '\n';
} while (std::next_permutation(std::begin(data), std::end(data)));
}
// Character data (string)
void print_all_permutations(std::string &data) {
std::stable_sort(std::begin(data), std::end(data));
do {
std::copy(data.begin(), data.end(), std::ostream_iterator<char>(std::cout, " ")), std::cout << '\n';
} while (std::next_permutation(std::begin(data), std::end(data)));
}
int main()
{
std::vector<int> v({1,2,3,4});
print_all_permutations(v);
std::string s("abcd");
print_all_permutations(s);
return 0;
}
我们可以在线性时间内找到序列的下一个排列。
Here is an answer 来自@le_m。可能会有帮助。
The following very efficient algorithm uses Heap's method to generate all permutations of N elements with runtime complexity in O(N!):
function permute(permutation) {
var length = permutation.length,
result = [permutation.slice()],
c = new Array(length).fill(0),
i = 1, k, p;
while (i < length) {
if (c[i] < i) {
k = i % 2 && c[i];
p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
result.push(permutation.slice());
} else {
c[i] = 0;
++i;
}
}
return result;
}
console.log(JSON.stringify(permute([1, 2, 3, 4])));
您可以使用堆栈进行排列。
在不依赖递归的情况下处理树或其他问题时，这种方法是理想的。
您将需要进行调整以消除任何重复值。
type permutation = [string, string[]]
function p(str: string): string[]{
const res: string[] = []
const stack: permutation[] = [["", str.split('')]]
while(stack.length){
const [head, tail] = stack.pop()
if(!tail.length){
res.push(head)
continue
}
for(let i = 0; i < tail.length; i++){
let newTail = tail.slice()
newTail.splice(i, 1)
stack.push([head + tail[i], newTail])
}
}
return res
}
要求：生成集合所有可能组合的算法，不重复，或递归调用函数以得到 return 结果。
Permutations in JavaScript? 中提供的大多数（如果不是全部）答案都是从循环或其他函数中递归调用函数以得到 return 结果。
循环内递归函数调用示例[=90=]
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 应该 return 6 ，或者 arr ["a", "b", "c"]
根据为集合确定的单个排列的总数，可以使用 Array.prototype.slice() 、Array.prototype.concat() 和 Array.prototype.reverse()[ 创建并填充包含所有六个排列的结果数组=90=]
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++ 实用算法 Calculating Permutations and Job Interview Questions 中发表的算法。
如果输入集是 ，似乎有一个可以扩展的模式，例如
["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 filled ;每个调用 .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);
编辑、更新
找到了一个过程，使用单个 for 循环，将上述模式用于 return 字典顺序的排列，最多为 .length 4 的输入。对于 .length of 5 的数组，预期结果未 returned。
该形态基于 "Calculating Permutations and Job Interview Questions"[0].[=90 处的第二张图表=]
不希望使用 .splice() 或 .sort() 到 return 结果，尽管在此处使用时试图遵守最后的 "rotate" 每列的要求。变量 r 应该引用下一个排列的第一个元素的 index，它确实如此。
如果.splice()、.sort()的用法遵循图表中的模式，则可以包括在内；尽管在 js 下面，他们实际上没有。
不完全确定下面 js 的问题只是 if (i % (total / len) === reset) 之后的语句，尽管这部分需要投入最多的时间；但仍然没有 return 预期结果。
具体来说，现在参考图表，在旋转时，例如 2 到索引 0，1 到索引 2。尝试通过使用负索引 r 从右向左遍历以检索应位于相邻 index 0 的下一个项目来实现此目的 "column" .
在下一列中，2 将放置在 index 2 处，3 将放置在 index 0 处。这是部分，就目前为止能够掌握或调试的，是出错的地方。
同样，return[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)
资源：
Generating Permutation with Javascript
(倒计时)快烫头词典编纂： (正式Example_03~回文)
Generating all Permutations [non-recursive]
（尝试从 C++ 移植到 javascript jsfiddle http://jsfiddle.net/tvvvjf3p/）
Calculating Permutation without Recursion - Part 2
permutations of a string using iteration
Evaluation of permutation algorithms
Permutation algorithm without recursion? Java
Non-recursive algorithm for full permutation with repetitive elements?
String permutations in Java (non-recursive)
Generating permutations lazily
How to generate all permutations of a list in Python
Can all permutations of a set or string be generated in O(n log n) time?
我认为这个 post 应该对您有所帮助。该算法应该很容易翻译成 JavaScript（我认为它已经超过 70% JavaScript 兼容）。
如果您追求效率，slice 和 reverse 是不好的调用。 post 中描述的算法遵循 next_permutation 函数的最有效实现，甚至集成在某些编程语言中（例如 C++）
编辑
当我再次迭代算法时，我认为你可以只删除变量的类型，你应该很好地进入 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;
}
这是我自己想出的一种方法的片段，但自然也能找到它 described elsewhere:
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 (e.g. 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>
说明
由于给定数组 arr 有 factorial(arr.length) 个排列，0 和 factorial(arr.length)-1 之间的每个数字都编码一个特定的排列。要取消对排列数的编码，请重复从 arr 中删除元素，直到没有元素为止。要删除的元素的确切索引由公式 (permNumber % factorial(arr.length)) / factorial(arr.length-1) 给出。可以使用其他公式来确定要删除的索引，只要它保留数字和排列之间的一对一映射即可。
例子
以下是如何为数组 (a,b,c,d) 生成所有排列：
# Perm 1st El 2nd El 3rd El 4th El
0 abcd (a,b,c,d)[0] (b,c,d)[0] (c,d)[0] (d)[0]
1 abdc (a,b,c,d)[0] (b,c,d)[0] (c,d)[1] (c)[0]
2 acbd (a,b,c,d)[0] (b,c,d)[1] (b,d)[0] (d)[0]
3 acdb (a,b,c,d)[0] (b,c,d)[1] (b,d)[1] (b)[0]
4 adbc (a,b,c,d)[0] (b,c,d)[2] (b,c)[0] (c)[0]
5 adcb (a,b,c,d)[0] (b,c,d)[2] (b,c)[1] (b)[0]
6 bacd (a,b,c,d)[1] (a,c,d)[0] (c,d)[0] (d)[0]
7 badc (a,b,c,d)[1] (a,c,d)[0] (c,d)[1] (c)[0]
8 bcad (a,b,c,d)[1] (a,c,d)[1] (a,d)[0] (d)[0]
9 bcda (a,b,c,d)[1] (a,c,d)[1] (a,d)[1] (a)[0]
10 bdac (a,b,c,d)[1] (a,c,d)[2] (a,c)[0] (c)[0]
11 bdca (a,b,c,d)[1] (a,c,d)[2] (a,c)[1] (a)[0]
12 cabd (a,b,c,d)[2] (a,b,d)[0] (b,d)[0] (d)[0]
13 cadb (a,b,c,d)[2] (a,b,d)[0] (b,d)[1] (b)[0]
14 cbad (a,b,c,d)[2] (a,b,d)[1] (a,d)[0] (d)[0]
15 cbda (a,b,c,d)[2] (a,b,d)[1] (a,d)[1] (a)[0]
16 cdab (a,b,c,d)[2] (a,b,d)[2] (a,b)[0] (b)[0]
17 cdba (a,b,c,d)[2] (a,b,d)[2] (a,b)[1] (a)[0]
18 dabc (a,b,c,d)[3] (a,b,c)[0] (b,c)[0] (c)[0]
19 dacb (a,b,c,d)[3] (a,b,c)[0] (b,c)[1] (b)[0]
20 dbac (a,b,c,d)[3] (a,b,c)[1] (a,c)[0] (c)[0]
21 dbca (a,b,c,d)[3] (a,b,c)[1] (a,c)[1] (a)[0]
22 dcab (a,b,c,d)[3] (a,b,c)[2] (a,b)[0] (b)[0]
23 dcba (a,b,c,d)[3] (a,b,c)[2] (a,b)[1] (a)[0]
请注意，每个排列 # 的形式为：
(firstElIndex * 3!) + (secondElIndex * 2!) + (thirdElIndex * 1!) + (fourthElIndex * 0!)
基本上就是解释中给出的公式的逆过程
创建排列的一种方法是将每个元素添加到目前所有结果中元素之间的所有空格中。这可以在没有递归的情况下使用循环和队列来完成。
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'])));
这可能是另一个解决方案，灵感来自 Steinhaus-Johnson-Trotter algorithm:
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 />");
}
我敢再补充一个答案，旨在回答你关于slice、concat、reverse的问题。
答案是可以（几乎），但效果不会太好。您在算法中所做的如下：
- 从右到左查找排列数组中的第一个反转（本例中的反转定义为
iandjwherei<jandperm[i]>perm[j]，索引从左到右） - 放置倒数较大的数
- 以相反的顺序连接处理过的数字，这将与排序顺序相同，因为没有观察到倒置。
- 连接反转的第二个数字（仍然按照前面的数字排序，因为没有观察到反转）
这主要是我的第一个答案所做的，但以更优化的方式进行。
例子
考虑排列 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 here。
这是计算字符串第 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!，一组len个不同元素共有factorial(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;
}
没有递归的相当简单的 C++ 代码。
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
// Integer data
void print_all_permutations(std::vector<int> &data) {
std::stable_sort(std::begin(data), std::end(data));
do {
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")), std::cout << '\n';
} while (std::next_permutation(std::begin(data), std::end(data)));
}
// Character data (string)
void print_all_permutations(std::string &data) {
std::stable_sort(std::begin(data), std::end(data));
do {
std::copy(data.begin(), data.end(), std::ostream_iterator<char>(std::cout, " ")), std::cout << '\n';
} while (std::next_permutation(std::begin(data), std::end(data)));
}
int main()
{
std::vector<int> v({1,2,3,4});
print_all_permutations(v);
std::string s("abcd");
print_all_permutations(s);
return 0;
}
我们可以在线性时间内找到序列的下一个排列。
Here is an answer 来自@le_m。可能会有帮助。
The following very efficient algorithm uses Heap's method to generate all permutations of N elements with runtime complexity in O(N!):
function permute(permutation) {
var length = permutation.length,
result = [permutation.slice()],
c = new Array(length).fill(0),
i = 1, k, p;
while (i < length) {
if (c[i] < i) {
k = i % 2 && c[i];
p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
result.push(permutation.slice());
} else {
c[i] = 0;
++i;
}
}
return result;
}
console.log(JSON.stringify(permute([1, 2, 3, 4])));
您可以使用堆栈进行排列。
在不依赖递归的情况下处理树或其他问题时，这种方法是理想的。 您将需要进行调整以消除任何重复值。
type permutation = [string, string[]]
function p(str: string): string[]{
const res: string[] = []
const stack: permutation[] = [["", str.split('')]]
while(stack.length){
const [head, tail] = stack.pop()
if(!tail.length){
res.push(head)
continue
}
for(let i = 0; i < tail.length; i++){
let newTail = tail.slice()
newTail.splice(i, 1)
stack.push([head + tail[i], newTail])
}
}
return res
}