我需要获取数组的所有可能的子集。
说我有这个：
[1, 2, 3]
我如何得到这个？
[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]
我对所有子集都感兴趣。对于特定长度的子集，请参考以下问题：
这是另一种非常优雅的解决方案，没有循环或递归，仅使用map和reduce数组本机函数。
const getAllSubsets =
theArray => theArray.reduce(
(subsets, value) => subsets.concat(
subsets.map(set => [value,...set])
),
[[]]
);
console.log(getAllSubsets([1,2,3]));我们可以从
offset使用生成器函数允许我们以恒定的内存使用量迭代子集：
// Generate all array subsets:
function* subsets(array, offset = 0) {
while (offset < array.length) {
let first = array[offset++];
for (let subset of subsets(array, offset)) {
subset.push(first);
yield subset;
}
}
yield [];
}
// Example:
for (let subset of subsets([1, 2, 3])) {
console.log(subset);
}运行时复杂度与解决方案数量 (2ⁿ) 乘以每个解决方案的平均长度 (n/2) = O(n2ⁿ)。
无需递归的简单解决方案：
function getAllSubsets(array) {
const subsets = [[]];
for (const el of array) {
const last = subsets.length-1;
for (let i = 0; i <= last; i++) {
subsets.push( [...subsets[i], el] );
}
}
return subsets;
}
它是如何工作的？
如果我们有一些从输入数字生成的子集，并且我们想在输入数组中再添加一个数字，这意味着我们可以获取所有现有的子集，并通过将新数字附加到每个现有子集来生成新的子集。
这是一个示例
[1, 2, 3]从空子集开始：
[]通过向每个现有子集添加“1”来创建新子集。它将是：
[][1]通过向每个现有子集添加“2”来创建新子集。它将是：
[], [1][2], [1, 2]通过向每个现有子集添加“3”来创建新子集。它将是：
[], [1], [2], [1, 2][3], [1, 3], [2, 3], [1, 2, 3]另一个简单的解决方案。
function getCombinations(array) {
function fork(i, t) {
if (i === array.length) {
result.push(t);
return;
}
fork(i + 1, t.concat([array[i]]));
fork(i + 1, t);
}
var result = [];
fork(0, []);
return result;
}
var data = [1, 2, 3],
result = getCombinations(data);
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }您可以使用如下内容轻松地从数组生成幂集：
var arr = [1, 2, 3];
function generatePowerSet(array) {
var result = [];
result.push([]);
for (var i = 1; i < (1 << array.length); i++) {
var subset = [];
for (var j = 0; j < array.length; j++)
if (i & (1 << j))
subset.push(array[j]);
result.push(subset);
}
return result;
}
console.log(generatePowerSet(arr));在函数的主循环中，会创建子集，然后将其推入
result我开始了解这篇文章中的示例发生了什么。虽然函数生成器示例、按位运算符示例以及数组映射和归约函数的示例使用非常优雅且令人印象深刻，但我发现很难在脑海中直观地看到到底发生了什么。我下面有两个例子，我相信它们很容易可视化非递归和递归解决方案。我希望这可以帮助其他人尝试了解查找所有子集的过程。
非递归： 对于数组的每个值，克隆所有现有子集（包括空集）并将新值添加到每个克隆，将克隆推回结果。
const PowerSet = array => {
const result = [[]] // Starting with empty set
for (let value of array) { // For each value of the array
const length = result.length // Can't use result.length in loop since
// results length is increased in loop
for (let i = 0; i < length; i++){
let temp = result[i].slice(0) // Make a clone of the value at index i
temp.push(value) // Add current value to clone
result.push(temp) // Add clone back to results array
}
}
return result;
}
console.log(PowerSet([1,2,3]))
递归地： 通过递归地推送当前索引值与不断增加的前缀值数组的组合来构建幂集。
const powerSetRecursive = (arr, prefix=[], set=[[]]) => {
if(arr.length === 0) return// Base case, end recursion
for (let i = 0; i < arr.length; i++) {
set.push(prefix.concat(arr[i]))// If a prefix comes through, concatenate value
powerSetRecursive(arr.slice(i + 1), prefix.concat(arr[i]), set)
// Call function recursively removing values at or before i and adding
// value at i to prefix
}
return set
}
console.log(powerSetRecursive([1,2,3]))
function subSets(num){
/*
example given number : [1,3]
[]
1: copy push 1
[] [1]
3: copy push 3
[] [1] [3] [1,3]
*/
let result = [];
result.push([]);
for(let i=0; i < num.length;i++){
let currentNum = num[i];
let len = result.length;
for(let j=0; j < len; j++){
let cloneData = result[j].slice();
cloneData.push(currentNum);
result.push(cloneData)
}
}
return result;
}
let test = [1,3];
console.log(subSets(test))//[ [], [ 1 ], [ 3 ], [ 1, 3 ] ]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;
}
使用
flatMaprestspreadconst 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])]
@koorchik的答案的简短版本。
var getAllSubsets = (nums) => {
const subsets = [[]];
for (n of nums) {
subsets.map((el) => {
subsets.push([...el, n]);
});
}
return subsets;
};
console.log(getAllSubsets([1, 2, 3]));
// [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]for循环：
function powerSet(numbers) {
const subsets = [[]]
for (const number of numbers) {
subsets.forEach(subset => subsets.push([...subset, number]))
}
return subsets
}
递归：
function powerSet(numbers) {
const subsets = [[]]
if (numbers.length === 0) return subsets
for (let i = 0; i < numbers.length; i++) {
subsets.push(...powerSet(numbers.slice(i + 1)).map(subset => [numbers[i], ...subset]))
// Or step by step:
// const number = numbers[i]
// const otherNumbers = numbers.slice(i + 1)
// const otherNumbersSubsets = powerSet(otherNumbers)
// const otherNumbersSubsetsWithNumber = otherNumbersSubsets.map(subset => [number, ...subset])
// subsets.push(...otherNumbersSubsetsWithNumber)
}
return subsets
}
使用reduceRight：
const subsets = array =>
array.reduceRight(
(accumulator, a) => [...accumulator, ...accumulator.map(b => [a, ...b])],
[[]]
);
console.log(subsets([1, 2, 3])); // [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]这个是递归的
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
ES2020 BigInts 已经可用。
Bigint 没有固定的存储大小（以位为单位）；它们的大小适应它们代表的整数。
- 阿克塞尔·劳施梅尔博士；适合缺乏耐心的程序员的 JavaScript - 第 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; } function getAllSubsets(arr) {
let subset = [[]];
function generateSubsets(indx, currentSubset) {
if (indx == arr.length) {
return;
}
for (let i = indx; i < arr.length; i++) {
currentSubset.push(arr[i])
subset.push([...currentSubset])
generateSubsets(i+1,currentSubset)
currentSubset.pop()
}
}
generateSubsets(0, [])
return subset
}
// Example usage:
const inputArray = [1, 2, 3];
const subsets = getAllSubsets(inputArray);
console.log(subsets);
const numArray = [1,2,3]
//const subArray =[[1],[1,2],[1,2,3],[2],[2,3],[3]]
let result = []
for(let i=0; i<=numArray.length; i++){
for( let j = i+1; j<=numArray.length; j++){
result.push(numArray.slice(i,j))
}
}
console.log(result)`enter code here`