Iterative Approach
The concept involves utilizing binary numbers to systematically generate the power set of a provided set of elements in a lexicographically ordered manner.
Steps:
- The string is sorted in lexicographic order by converting it into an array, sorting it, and joining it back into a string.
- Now generates all possible binary representations of subsets by looping integers from 0 to 2^n – 1, where n is the length of the string.
- For each binary representation, it creates the corresponding subset, where ‘1’s indicate character inclusion, and ‘0’s indicate exclusion.
- The subsets are sorted in lexicographic order and then printed to the console.
Example: In this code we print the power set in lexicographical order with iterative approach by using JavaScript.
Javascript
function generatePowerSet(s) { // Sort the string in lexicographical order s = s.split('').sort().join(''); const n = s.length; const subsets = []; // Generate all possible binary strings of // length n for (let i = 0; i < 2 ** n; i++) { // Convert the integer i to a binary // string of length n let binary = i.toString(2).padStart(n, '0'); let subset = ''; // Generate the subset based on the // binary string for (let j = 0; j < n; j++) { if (binary[j] === '1') { subset += s[j]; } } subsets.push(subset); } // Sort the subsets in lexicographically order subsets.sort(); // Print the subsets in sorted order for (let subset of subsets) { console.log(subset); } } const s = '123'; generatePowerSet(s); |
Output
1 12 123 13 2 23 3
JavaScript Program to Find Power Set in Lexicographic Order
Power set P(S) of a set S is the set of all subsets of S. For example S = {1, 2, 3} then P(s) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.
This JavaScript code generates and sorts the power set of an input string in lexicographic order, listing all possible subsets from the empty set to the full set. It uses a binary representation approach for efficient subset generation.
Examples:
Input: 123
Output : 1 12 123 13 2 23 3
Table of Content
- Recursive Approach
- Iterative Approach
- Bit manipulation