Generate powerset of a set in JavaScript
This post will discuss how to generate powerset of a set in JavaScript.
A powerset of a set is the set of all possible subsets of the original set, including the empty set and the original set itself. For example, the powerset of {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Here are some of the methods that we can use to generate the powerset of a set in JavaScript:
1. Using recursion
We can use a recursive function that takes an array as input and returns an array of arrays as output. The base case is when the input array is empty, then return an array containing an empty array. The recursive case is to take the first element of the input array and append it to each subset generated by the recursive call on the rest of the input array. Then concatenate the original subsets and the new subsets and return them. For instance:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Define a recursive function to generate the powerset function powerSet(array) { // Base case: if the input array is empty, return an array with an empty array if (array.length === 0) { return [[]]; } // Recursive case: take the first element of the input array let first = array[0]; // Make a recursive call on the rest of the input array let rest = powerSet(array.slice(1)); // Append the first element to each subset generated by the recursive call let newSubsets = rest.map(subset => [first, ...subset]); // Concatenate the original subsets and the new subsets and return them return [...rest, ...newSubsets]; } // [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]] console.log(powerSet([1, 2, 3])); |
2. Using bit manipulation
We can use bit manipulation to generate all possible combinations of elements in the input array. The idea is to use a binary number to represent each subset, where each bit corresponds to an element in the input array. If the bit is 1, then the element is included in the subset; if the bit is 0, then the element is excluded. For example, for an input array of [1, 2, 3], the binary number 101 represents the subset [1, 3]. To generate all possible binary numbers from 0 to 2^n-1, where n is the length of the input array, we can use a for loop and bitwise operations. For each binary number, we can iterate over its bits and check which elements to include in the subset. For instance:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Define a function to generate the powerset using bit manipulation function powerSet(array) { // Initialize an empty array to store the subsets let subsets = []; // Get the length of the input array let n = array.length; // Loop from 0 to 2^n - 1 for (let i = 0; i < Math.pow(2, n); i++) { // Initialize an empty array to store the current subset let subset = []; // Loop over each bit of i for (let j = 0; j < n; j++) { // Check if j-th bit of i is set (i.e., equal to 1) if (i & (1 << j)) { // If yes, then include j-th element of the input array in the subset subset.push(array[j]); } } // Add the subset to the subsets array subsets.push(subset); } // Return the subsets array return subsets; } // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] console.log(powerSet([1, 2, 3])); |
3. Using generator function
We can use a generator function to generate a power set by taking an array as an argument and yielding each subset as an array. The idea is similar to the recursive function, but instead of returning an array of arrays, we yield each subset using the yield keyword. This way, we can iterate over the subsets with constant memory usage.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Generator function to generate the powerset function* powerSet(array, offset = 0) { while (offset < array.length) { // take the first element let first = array[offset++]; // get the subsets of the rest for (let subset of powerSet(array, offset)) { // append the first element to each subset subset.push(first); // yield each subset yield subset; } } // yield the empty subset yield []; } for (let subset of powerSet([1, 2, 3])) { console.log(subset); // [3, 2, 1], [2, 1], [3, 1], [1], [3, 2], [2], [3], [] } |
That’s all about generating powerset of a set in JavaScript.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)