JavaScript中的排列？我正在编写一个函数，它执行以下操作：将整数数组作为参数(例如[1，2，3，4])创建所有可能的[1，2，3，4]排列的数组，每个置换的长度为4下面的函数(我在网上找到的)通过接受一个字符串作为参数，并返回该字符串的所有排列来实现这一点。我想不出如何修改它，使其与整数数组一起工作(我认为这与某些方法在字符串上的工作方式与它们在整数上的工作方式不同有关，但我不确定.)var permArr = [], usedChars = [];function permute(input) {
var i, ch, chars = input.split("");
for (i = 0; i < chars.length; i++) {
ch = chars.splice(i, 1);
usedChars.push(ch);
if (chars.length == 0)
permArr[permArr.length] = usedChars.join("");
permute(chars.join(""));
chars.splice(i, 0, ch);
usedChars.pop();
}
return permArr};注意：我希望使函数返回数组整数, 不一列弦.我真的需要使用JavaScript的解决方案。我已经想出了如何在python中做到这一点。
2 回答
陪伴而非守候
TA贡献1757条经验 获得超8个赞
如果您注意到，代码实际上在进行任何排列之前将字符拆分成一个数组，因此您只需删除联接和拆分操作即可。
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
permute(input);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
document.write(JSON.stringify(permute([5, 3, 7, 1])));
当年话下
TA贡献1890条经验 获得超9个赞
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(permute([1, 2, 3]));
function* permute(permutation) {
var length = permutation.length,
c = Array(length).fill(0),
i = 1, k, p;
yield permutation.slice();
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;
yield permutation.slice();
} else {
c[i] = 0;
++i;
}
}
}
// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);
// Simple array conversion:
var permutations = [...permute([1, 2, 3])];
function permute_SiGanteng(input) {
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
permute(input);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
}
return permute(input);
}
function permute_delimited(inputArr) {
var results = [];
function permute(arr, memo) {
var cur, memo = memo || [];
for (var i = 0; i < arr.length; i++) {
cur = arr.splice(i, 1);
if (arr.length === 0) {
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);
}
return results;
}
return permute(inputArr);
}
function permute_monkey(inputArray) {
return inputArray.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
return [item].concat(perm);
}) || item);
}, []);
}
function permute_Oriol(input) {
var permArr = [],
usedChars = [];
return (function main() {
for (var i = 0; i < input.length; i++) {
var ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
main();
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr;
})();
}
function permute_MarkusT(input) {
function permutate(array, callback) {
function p(array, index, callback) {
function swap(a, i1, i2) {
var t = a[i1];
a[i1] = a[i2];
a[i2] = t;
}
if (index == array.length - 1) {
callback(array);
return 1;
} else {
var count = p(array, index + 1, callback);
for (var i = index + 1; i < array.length; i++) {
swap(array, i, index);
count += p(array, index + 1, callback);
swap(array, i, index);
}
return count;
}
}
if (!array || array.length == 0) {
return 0;
}
return p(array, 0, callback);
}
var result = [];
permutate(input, function(a) {
result.push(a.slice(0));
});
return result;
}
function permute_le_m(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;
}
function permute_Urielzen(arr) {
var finalArr = [];
var iterator = function (arrayTaken, tree) {
for (var i = 0; i < tree; i++) {
var temp = arrayTaken.slice();
temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
if (tree >= arr.length) {
finalArr.push(temp);
} else { iterator(temp, tree + 1); }
}
}
iterator(arr, 1); return finalArr;
}
function permute_Taylor_Hakes(arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permute_Taylor_Hakes(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;
}
var Combinatorics = (function () {
'use strict';
var version = "0.5.2";
/* combinatory arithmetics */
var P = function(m, n) {
var p = 1;
while (n--) p *= m--;
return p;
};
var C = function(m, n) {
if (n > m) {
return 0;
}
return P(m, n) / P(n, n);
};
var factorial = function(n) {
return P(n, n);
};
var factoradic = function(n, d) {
var f = 1;
if (!d) {
for (d = 1; f < n; f *= ++d);
if (f > n) f /= d--;
} else {
f = factorial(d);
}
var result = [0];
for (; d; f /= d--) {
result[d] = Math.floor(n / f);
n %= f;
}
return result;
};
/* common methods */
var addProperties = function(dst, src) {
Object.keys(src).forEach(function(p) {
Object.defineProperty(dst, p, {
value: src[p],
configurable: p == 'next'
});
});
};
var hideProperty = function(o, p) {
Object.defineProperty(o, p, {
writable: true
});
};
var toArray = function(f) {
var e, result = [];
this.init();
while (e = this.next()) result.push(f ? f(e) : e);
this.init();
return result;
};
var common = {
toArray: toArray,
map: toArray,
forEach: function(f) {
var e;
this.init();
while (e = this.next()) f(e);
this.init();
},
filter: function(f) {
var e, result = [];
this.init();
while (e = this.next()) if (f(e)) result.push(e);
this.init();
return result;
},
lazyMap: function(f) {
this._lazyMap = f;
return this;
},
lazyFilter: function(f) {
Object.defineProperty(this, 'next', {
writable: true
});
if (typeof f !== 'function') {
this.next = this._next;
} else {
if (typeof (this._next) !== 'function') {
this._next = this.next;
}
var _next = this._next.bind(this);
this.next = (function() {
var e;
while (e = _next()) {
if (f(e))
return e;
}
return e;
}).bind(this);
}
Object.defineProperty(this, 'next', {
writable: false
});
return this;
}
};
/* power set */
var power = function(ary, fun) {
var size = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
that.index = 0;
},
nth: function(n) {
if (n >= size) return;
var i = 0,
result = [];
for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
},
next: function() {
return this.nth(this.index++);
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* combination */
var nextIndex = function(n) {
var smallest = n & -n,
ripple = n + smallest,
new_smallest = ripple & -ripple,
ones = ((new_smallest / smallest) >> 1) - 1;
return ripple | ones;
};
var combination = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var first = (1 << nelem) - 1,
size = C(ary.length, nelem),
maxIndex = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
this.index = first;
},
next: function() {
if (this.index >= maxIndex) return;
var i = 0,
n = this.index,
result = [];
for (; n; n >>>= 1, i++) {
if (n & 1) result[result.length] = this[i];
}
this.index = nextIndex(this.index);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* permutation */
var _permutation = function(ary) {
var that = ary.slice(),
size = factorial(that.length);
that.index = 0;
that.next = function() {
if (this.index >= size) return;
var copy = this.slice(),
digits = factoradic(this.index, this.length),
result = [],
i = this.length - 1;
for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
this.index++;
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
};
return that;
};
// which is really a permutation of combination
var permutation = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var size = P(ary.length, nelem),
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'cmb');
hideProperty(that, 'per');
addProperties(that, {
valueOf: function() {
return size;
},
init: function() {
this.cmb = combination(ary, nelem);
this.per = _permutation(this.cmb.next());
},
next: function() {
var result = this.per.next();
if (!result) {
var cmb = this.cmb.next();
if (!cmb) return;
this.per = _permutation(cmb);
return this.next();
}
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* export */
var Combinatorics = Object.create(null);
addProperties(Combinatorics, {
C: C,
P: P,
factorial: factorial,
factoradic: factoradic,
permutation: permutation,
});
return Combinatorics;
})();
var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];
suite.add('permute_SiGanteng', function() {
permute_SiGanteng(input);
})
.add('permute_delimited', function() {
permute_delimited(input);
})
.add('permute_monkey', function() {
permute_monkey(input);
})
.add('permute_Oriol', function() {
permute_Oriol(input);
})
.add('permute_MarkusT', function() {
permute_MarkusT(input);
})
.add('permute_le_m', function() {
permute_le_m(input);
})
.add('permute_Urielzen', function() {
permute_Urielzen(input);
})
.add('permute_Taylor_Hakes', function() {
permute_Taylor_Hakes(input);
})
.add('permute_Combinatorics', function() {
Combinatorics.permutation(input).toArray();
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run({async: true});
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>
99.152毫秒 这种算法
153.115毫秒 401.255毫秒 497.037ms 925.669ms 1026.571毫秒 2529.841毫秒 3992.622ms 4514.665ms
添加回答
举报
0/150
提交
取消