在javascript中查找与排列
Find ith permutation in javascript
给定大小为n
的数组arr
,索引为0<=i<n!
,我想返回第I个排列
我可以写一个方法来获取所有的排列:
function permute (arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permute(arr.slice(0, i).concat(arr.slice(i + 1)));
for (var j = 0; j < subPerms.length; j++) {
subPerms[j].unshift(arr[i]);
permutations.push(subPerms[j]);
}
}
return permutations;
}
如何将其裁剪为只得到一个递归分支?
可以使用数组长度的阶乘作为获取目标排列的帮助。基本上,该算法计算数组索引,根据索引重新组装结果。
function getN(n, array) {
var f,
l = array.length,
indices = [];
array = array.slice();
while (l--) {
f = factorial(l);
indices.push(Math.floor(n / f));
n %= f;
}
return indices.map(function (i) {
return array.splice(i, 1)[0];
});
}
function factorial(num) {
var result = 1;
while (num) {
result *= num;
num--;
}
return result;
}
var i, l,
array = [1, 2, 3, 4];
for (i = 0, l = factorial(array.length); i < l; i++) {
console.log(i, '>', getN(i, array).join(' '));
}
.as-console-wrapper { max-height: 100% !important; top: 0; }
计算开销较小的答案是:使用布尔标志数组跟踪已使用的元素。这似乎并没有多大的改进,因为您仍然需要扫描标志数组以获得您要查找的元素,从而导致O(N^2)的性能。但是,如果您利用数组中元素的布局,您可能会得到一些改进:
function getN(n, array) {
var f,
l = array.length,
indices = [];
//Instead of using splice() to remove elements that are
//already in the permutation, I'll use an array of bit flags
//to track used elements.
var indexMask = [];
indexMask.length = array.length;
var indexMaskInit = 0;
for(indexMaskInit = 0; indexMaskInit < indexMask.length;
indexMaskInit++) {
indexMask[indexMaskInit] = true;
}
array = array.slice();
while(l--) {
f = factorial(l);
indices.push(Math.floor(n / f));
n %= f;
}
var toReturn = [];
toReturn.length = array.length;
//Now, extract the elements using the array of indices.
var numUsed;
for(numUsed = 0; numUsed < indices.length; numUsed++) {
//factIndex is the index in the set of elements that have
//not been selected yet.
var factIndex = indices[numUsed];
var elementFound = false;
//This code searches for the element by assuming that some
//elements have already been selected. The number of used
//elements can be found using the index of the outer loop.
//By counting the number of used elements at the beginning
//of the array, it may be possible to calculate an offset
//that can be used to find the desired element.
if(factIndex > 2 * numUsed)
{
var offset = 0, scanIndex;
//Boundary condition: no elements have been used yet,
//in which case we can use factIndex directly.
if(numUsed === 0) {
elementFound = true;
}
else {
//Loop to 2*numUsed, to avoid a linear search.
for(scanIndex = 0; scanIndex < 2 * numUsed;
scanIndex++) {
if(!indexMask[scanIndex]) {
offset++;
}
//Boundary condition: all used elements have
//been found.
if(offset >= numUsed) {
elementFound = true;
break;
}
}
}
if(elementFound) {
factIndex += offset;
}
}
//This code starts at the end of the array and counts the
//number of used elements.
else if ((indices.length - 1 - factIndex) > 2 * numUsed) {
var offset = 0, scanIndex;
//Boundary condition: no elements have been used yet,
//in which case we can use factIndex directly.
if(numUsed === 0) {
elementFound = true;
}
else {
var n = indices.length - 1;
//Loop to 2*numUsed, to avoid a linear search.
for(scanIndex = n; scanIndex > n - 2 * numUsed;
scanIndex--) {
if(!indexMask[scanIndex]) {
offset++;
}
//Boundary condition: all used elements have
//been found.
if(offset >= numUsed) {
elementFound = true;
break;
}
}
}
if(elementFound) {
factIndex += (numUsed - offset);
}
}
//If the number of used elements is not much greater than
//factIndex, or they do not all cluster at the beginning
//of the array, it may be better to run a linear search.
if(!elementFound)
{
var searchIndex = 0, i;
for(i = 0; i < indexMask.length; i++) {
if(indexMask[i]) {
if(searchIndex >= factIndex) {
break;
}
else {
searchIndex++;
}
}
}
factIndex = i;
}
toReturn[numUsed] = array[factIndex];
indexMask[factIndex] = false;
}
return toReturn;
}
function factorial(num) {
var result = 1;
while (num) {
result *= num;
num--;
}
return result;
}
var i, l;
var array = [1, 2, 3, 4];
//var array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
for (i = 0, l = factorial(array.length); i < l; i++) {
console.log(i, getN(i, array).join(' '));
}
Try (algorithm from here)
function perm(n,arr) {
let r=[],i=1;
while (n) { r.unshift(n%i); n=n/i++|0 }
let s= i-1 ? arr.splice(-r.length) : arr;
return arr.concat(r.map( x=> s.splice(x,1)[0] ));
}
// TEST
for(let i=0; i<4*3*2*1; i++) console.log( i, perm(i,[1,2,3,4]).join() );
相关文章:
- 正在全局范围中查找JavaScript函数
- Javascript(Angular)从一个对象数组到第二个数组查找值
- 如何删除多行HTML排列中的空白
- 在不使用jquery的情况下查找页面中的所有锚点并附加函数
- es6 相当于下划线查找位置
- 在DOM中查找一个模式并替换它's的内容使用jquery
- 如何使用jquery迭代具有相同属性的html元素并查找onclick事件
- 如何在不传递此信息的情况下查找被调用的元素
- Lodash 从值数组中查找数组中的值
- 如何使用JavaScript查找1和N之间的所有数字的总和
- 使用RegExp查找url中的字符
- 查找元素高度,包括边距
- 使用JS查找数组的平均值
- 查找最短和最长日期
- 查找一组数字和运算符的所有排列
- JavaScript/jQuery:查找列大小差异最小的排列
- 在具有重复项的所有可能排列的列表中查找给定字符串的秩
- 在所有可能排列的列表中查找给定字符串的秩
- 在javascript中查找与排列
- 查找两个数组的可用组合(排列?)