14个回答
1
let subsets = (n) => {
let result = [];
result.push([]);
n.forEach(a => {
//array length
let length = result.length;
let i =0;
while(i < length){
let temp = result[i].slice(0);
temp.push(a);
result.push(temp);
i++;
}
})
return result;
}
- ASHISH R
1
使用
或者，以不同的风格使用相同的算法，
flatMap 和 rest/spread，这可以相当优雅：
const subsets = ([x, ...xs]) =>
x == undefined
? [[]]
: subsets (xs) .flatMap (ss => [ss, [x, ...ss]])
console .log (subsets ([1, 2, 3])).as-console-wrapper {max-height: 100% !important; top: 0}这个版本不会按照要求的顺序返回它们。这样做似乎不太优雅，可能有更好的版本：
const subset = (xs = []) => {
if (xs.length == 0) {return [[]]}
const ys = subset (xs .slice (0, -1))
const x = xs .slice (-1) [0]
return [... ys, ... ys .map (y => [... y, x])]
}
或者，以不同的风格使用相同的算法，
const subsets = (
xs = [],
x = xs .slice (-1) [0],
ys = xs.length && subsets (xs .slice (0, -1))
) =>
xs .length == 0
? [[]]
: [... ys, ... ys .map (y => [... y, x])]
- Scott Sauyet
2
在我看来，你的第二个和第三个版本也没有按照 OP 要求返回子集的递增顺序。 - thund
@thund：你说得对。这些都有逻辑顺序，但没有一个与实际请求相匹配。我误读了那个。也许等我有时间了，我会寻找一个优雅的解决方案来解决这个问题。 - Scott Sauyet
0
更新 ES2020
ES2020 中引入了 BigInts。
BigInts 没有固定的位数存储大小；它们的大小适应于它们所表示的整数。
- Dr. Axel Rauschmayer; JavaScript for impatient programmers - Chapter 18.2 BigInts
请参见源。
使用 BitInts，我们可以使用 二进制计数器 计算幂集，并且不再受到最大整数大小的限制。
使用 生成器，我们还可以以恒定的内存需求循环遍历幂集，这对于生成巨大的幂集非常重要。
以下是一个使用原始数组 [1, 2, 3] 的示例。
/**
* Generate power set from a given array
* @param {Array<any>} array array to create power set from
*/
function* powerSet(array){
// use BigInt to be no longer limited by maximum length of 53-bits
const size = 2n ** BigInt(array.length);
for (let i = 0; i < size; i++) {
const cur = [];
for(let j = 0; j < array.length; j++){
// check if i-th bit is set to 1
if((i & (1 << j)) > 0){
// push array value (represented by that 1-bit) to result
cur.push(array[j]);
}
}
// generate next result
yield cur;
}
}
// generate power set for [1, 2, 3] and print results
console.log([...powerSet([1, 2, 3])]);.as-console-wrapper { max-height: 100% !important; top: 0; }以下是如何在常量内存和没有上限的情况下循环遍历非常大的幂集（理论上，计算时间将有一个上限）。
/**
* Generate power set from a given array
* @param {Array<any>} array array to create power set from
*/
function* powerSet(array){
// use BigInt to no longer limited by maximum length of 53-bits
const size = 2n ** BigInt(array.length);
for (let i = 0; i < size; i++) {
const cur = [];
for(let j = 0; j < array.length; j++){
// check if i-th bit is set to 1
if((i & (1 << j)) > 0){
// push array value (represented by that 1-bit) to result
cur.push(array[j]);
}
}
// generate next result
yield cur;
}
}
/**
* Helper function to generate an array containing more than 53 elements
* @param {number} start
* @param {number} end
*/
function* range(start, end){
for (let i = start; i < end; i++) {
yield i;
}
}
// create an array containing elments 1 through 60 ([1, 2, 3, ..., 60])
const oneToSixty = [...range(1, 61)];
let i = 0;
const max = 1000;
// loop over whole powerSet with constant memory requirement
// abort after 1000 subsets, otherwise this will take a very long time to complete
for(const subset of powerSet(oneToSixty)){
console.log(subset);
if(i++ === max) break;
}.as-console-wrapper { max-height: 100% !important; top: 0; }- Mushroomator
0
这个是使用递归的
var subsets = function(s){
if(s.length === 0) {
return [[]]
}
var h,t,ss_excl_h;
var ss_incl_h = [];
[h,...t] = s;
ss_excl_h = subsets(t)
for(ss of ss_excl_h) {
let hArr = [];
hArr.push(h);
let temp = hArr.concat(ss)
ss_incl_h.push(temp);
}
return ss_incl_h.concat(ss_excl_h)
}
console.log(subsets([1,2,3])) // returns distinct subsets
- pride
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
[1, 1]或者[1, 2, 1]的输出会是什么？ - ibrahim mahrir[1, 1]的幂集可能是[], [1], [1], [1, 1]- 但如果您有更好的想法，请发表。@ibrahimmahrir - le_m