Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find all subsets of a set in JavaScript? (Powerset of array)

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:

  • Finding subsets of size n: 1, 2
  • Finding subsets of size > 1: 1
like image 892
le_m Avatar asked Mar 13 '17 21:03

le_m


People also ask

How do you find the subset of the of the arrays?

The number of subsets of an array is 2N where N is the size of the array. We basically generate N-bit binary string for all numbers in the range 0 to 2N – 1 and print array based on the string. If the ith index of the binary string is 1, that means the ith index of the array is included in the subset.

How do you find all possible subsets?

If a set contains 'n' elements, then the number of subsets of the set is 2n. Number of Proper Subsets of the Set: If a set contains 'n' elements, then the number of proper subsets of the set is 2n - 1. In general, number of proper subsets of a given set = 2m - 1, where m is the number of elements.

How many subsets does an array of size n have?

Yes there is a formula for the maximum number of subsets given a set of size N. If you do not want to include the null set, then the answer would be 2N−1. If you wish to know the derivation of this formula, please see this question.

How many subsets does an array have?

So, in the case of an array, it would mean the number of elements in the array or the size of the array, 2^(size of the array) will be the number of subsets. Let us take in the case, an array of "a, b, c". Since this array has a size of 3, there would be 2^3=8 subsets.


1 Answers

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]));
like image 78
MennyMez Avatar answered Oct 09 '22 04:10

MennyMez