I need to get all possible subsets of an array.
Say I have this:
[1, 2, 3]
How do I get this?
[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]
I am interested in all subsets. For subsets of specific length, refer to the following questions:
Here is one more very elegant solution with no loops or recursion, only using the map and reduce array native functions.
const getAllSubsets =
theArray => theArray.reduce(
(subsets, value) => subsets.concat(
subsets.map(set => [value,...set])
),
[[]]
);
console.log(getAllSubsets([1,2,3]));reduce() and map() and not blame a very much logic and understandle solution for your misunderstanding. –
Belsen reduce, concat and map. If you think there's magic happening you should study a bit of functional programming. –
Gangway We can solve this problem for a subset of the input array, starting from offset. Then we recurse back to get a complete solution.
Using a generator function allows us to iterate through subsets with constant memory usage:
// 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);
}Runtime complexity is proportional to the number of solutions (2ⁿ) times the average length per solution (n/2) = O(n2ⁿ).
constant memory usage? –
Kelt for (let subset of subsets(array)) is bound by the length of array, let's say n and not 2^n which would be the case if we first build all subsets and then iterate over them. –
Titanothere O(n) memory growth. Per my perf testing, on the first iteration of the generator (i.e: .next()) we are instantiating all generator functions from 0...n. Unlike tail recursion which grows at O(1) memory growth, this seems to grow at O(n)... btw - I hope I'm wrong in this analysis because the generator approach seems like an elegant approach. (P.S: A quality article I found: medium.com/javascript-scene/…) –
Kelt O(1) memory growth" - memory complexity can't be O(1) as each subset already occupies O(n) space. What do you mean with "increasing at O(n) memory growth` - the total space complexity is in O(n) where n is the array length? –
Titanothere O(1) memory growth). Seems generators won't be optimized in the same way as a tail-call function. See: benignbemine.github.io/2015/07/19/es6-tail-calls –
Kelt Simple solution without recursion:
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;
}
How does it work?
If we have some subsets generated from input numbers and we want to add one more number to our input array, it means that we can take all already existing subsets and generate new ones by appending the new number to each of the existing.
Here is an example for [1, 2, 3]
Start with an empty subset: []
Create new subsets by adding "1" to each existing subset. It will be:[] [1]
Create new subsets by adding "2" to each existing subset. It will be:[], [1] [2], [1, 2]
Create new subsets by adding "3" to each existing subset. It will be: [], [1], [2], [1, 2] [3], [1, 3], [2, 3], [1, 2, 3]
subsets.slice(1). –
Synclastic Another simple solution.
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; }.as-console-wrapper? –
Titanothere You can easily generate the powerset from an array, using something like the following:
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));Throughout the main loop of the function, subsets are created and then pushed into the result array.
result.push(subset) out of the loop increment to the loop body would probably improve readability. And if you are already resorting to bitwise operations: Math.pow(2, j) == 1 << j –
Titanothere I set out to understand what is happening with the examples in this post. While the function generator example, bit-wise operator example, and the example use of the array map and reduce functions are very elegant and impressive, I found it tough to mentally visual what precisely was happening. I have 2 examples below that I believe are easy to visualize both a non-recursive and a recursive solution. I hope this helps others attempting to wrap their heads around the process of finding all subsets.
NON-RECURSIVE: For each value of the array clone all existing subsets (including the empty set) and add the new value to each of the clones, pushing the clones back to the results.
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]))
RECURSIVELY: Build the powerset by recursively pushing a combination of the current index value concatenated with an ever increasing prefix array of values.
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;
}
Using flatMap and rest/spread, this can be fairly elegant:
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}This version does not return them in the requested order. Doing that seems slightly less elegant, and there's probably a better version:
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])]
}
Or, the same algorithm in a different style,
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])]
A shorter version of @koorchik's answer.
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 loop:
function powerSet(numbers) {
const subsets = [[]]
for (const number of numbers) {
subsets.forEach(subset => subsets.push([...subset, number]))
}
return subsets
}
Recursion:
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
}
Using 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]]With ES2020 BigInts have become available.
Bigints don’t have a fixed storage size in bits; their sizes adapt to the integers they represent.
- Dr. Axel Rauschmayer; JavaScript for impatient programmers - Chapter 18.2 BigInts
See source.
Using BitInts we can use a binary counter to calculate the power set and are no longer limited by the maximum integer size.
Using a generator we can additionally loop over a power set with constant memory requirement which is important if you want to generate a huge power set.
Here an example using you original array [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; }Here how you could loop over a very large power set with constant memory and no upper bound (theoretically, there will be an upper bound in terms of compute time) for the array length.
/**
* 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; }This one is with recursion
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
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`
[] and [1,3] –
Gangway © 2022 - 2024 — McMap. All rights reserved.
[1, 1]or[1, 2, 1]...? – Enervate[1, 1]would probably be[], [1], [1], [1, 1]- but if you have a better idea, just post it. – Titanothere