gue*_*314 29 javascript algorithm permutation
要求:生成集合的所有可能组合的算法,无需重复,或递归调用函数以返回结果.
大多数,如果不是所有的答案都在JavaScript中的Permutations提供？从循环或其他函数中递归调用函数以返回结果.
循环内的递归函数调用示例
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()
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()返回结果.变量应该引用下一个排列的第一个元素,它就是这个元素.rindex
使用的.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)资源:
(倒计时)QuickPerm Head Lexicography :(正式例_03~回文)
生成所有排列[非递归]
(尝试移植C++到javascriptjsfiddle http://jsfiddle.net/tvvvjf3p/)
chq*_*lie 19
这是计算字符串第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)!具有任何给定元素作为其第一元素的不同排列.该算法非常简单,具有有趣的特性:
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;
}
我认为这篇文章可以帮到你.该算法应该可以轻松转换为JavaScript(我认为它已经超过70%已经与JavaScript兼容).
slicereverse如果你追求效率,那就是糟糕的使用召唤.帖子中描述的算法遵循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;
}
创建排列的一种方法是到目前为止在所有结果中的元素之间的所有空间中添加每个元素.这可以在没有使用循环和队列的递归的情况下完成.
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算法:
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 />");
}这是我自己提出的一种方法的片段,但自然也能够在其他地方找到它:
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>说明
由于有factorial(arr.length)排列对于给定的阵列arr,每一个之间数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!)
这基本上是解释中给出的公式的逆过程.
我敢添加另一种答案,旨在回答您的问题有关slice,concat,reverse.
答案是(几乎)可能,但它不会很有效.您在算法中执行的操作如下:
i和j其中i< j和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 这里.
| 归档时间： |
|
| 查看次数： |
4479 次 |
| 最近记录： |