Power Set Generation

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

def power_set(elements):
    """
    Generate the power set of the given elements.
    
    Args:
        elements: Any iterable of elements. Duplicates are preserved.
        
    Returns:
        List of lists, where each inner list is one subset.
        Subsets are ordered by binary encoding (empty set first, full set last).
        
    Time Complexity: O(n * 2^n) where n = len(elements)
    Space Complexity: O(n * 2^n) for storing all subsets
    
    Examples:
        >>> power_set([])
        [[]]
        >>> power_set([1])
        [[], [1]]
        >>> power_set([1, 2])
        [[], [1], [2], [1, 2]]
    """
    elements = list(elements)  # Ensure indexable; handle any iterable
    n = len(elements)
    
    # Edge case: empty input
    if n == 0:
        return [[]]  # Power set of empty set is {empty set}
    
    all_subsets = []
    
    def backtrack(index, current):
        """Recursive helper using include/exclude paradigm."""
        if index == n:
            # Make a copy to avoid reference issues
            all_subsets.append(current[:])  # Slice copy is efficient
            return
        
        # EXCLUDE current element first (for binary ordering where 000 comes first)
        backtrack(index + 1, current)
        
        # INCLUDE current element
        current.append(elements[index])
        backtrack(index + 1, current)
        current.pop()  # Restore state
    
    backtrack(0, [])
    return all_subsets
 
 
def power_set_bit_manipulation(elements):
    """
    Generate power set using bit manipulation.
    
    Alternative implementation that's often faster in practice due to
    simpler loop structure and no function call overhead.
    
    Args:
        elements: Iterable of elements
        
    Returns:
        List of lists representing all subsets
    """
    elements = list(elements)
    n = len(elements)
    total = 1 << n  # 2^n
    
    all_subsets = []
    for mask in range(total):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(elements[i])
        all_subsets.append(subset)
    
    return all_subsets
 
 
# Verification
if __name__ == "__main__":
    test_cases = [
        [],
        [1],
        [1, 2],
        ['a', 'b', 'c'],
    ]
    
    for tc in test_cases:
        ps = power_set(tc)
        ps_bit = power_set_bit_manipulation(tc)
        expected_count = 2 ** len(tc)
        
        assert len(ps) == expected_count, f"Count mismatch for {tc}"
        assert len(ps_bit) == expected_count, f"Bit count mismatch for {tc}"
        
        # Verify same subsets (as sets of frozensets for comparison)
        ps_set = {frozenset(s) for s in ps}
        ps_bit_set = {frozenset(s) for s in ps_bit}
        assert ps_set == ps_bit_set, f"Content mismatch for {tc}"
        
        print(f"✓ power_set({tc}) = {ps}")

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

def power_set_generator(elements):
    """
    Generate power set lazily using a generator.
    
    Each subset is yielded as it's constructed, avoiding storage of all 2^n subsets.
    
    Space Complexity: O(n) for the current subset + recursion stack
    Time Complexity: O(n * 2^n) total to iterate through all subsets
    
    Usage:
        for subset in power_set_generator([1, 2, 3]):
            process(subset)  # Each subset yielded one at a time
    """
    elements = list(elements)
    n = len(elements)
    
    def backtrack(index, current):
        if index == n:
            yield current[:]  # Yield a copy of current subset
            return
        
        # Exclude branch
        yield from backtrack(index + 1, current)
        
        # Include branch
        current.append(elements[index])
        yield from backtrack(index + 1, current)
        current.pop()
    
    yield from backtrack(0, [])
 
 
def power_set_generator_iterative(elements):
    """
    Iterative generator using bit manipulation.
    
    No recursion, minimal memory footprint.
    """
    elements = list(elements)
    n = len(elements)
    
    for mask in range(1 << n):
        subset = [elements[i] for i in range(n) if mask & (1 << i)]
        yield subset
 
 
# Example usage
def count_subsets_with_sum(elements, target):
    """
    Count subsets summing to target WITHOUT storing all subsets.
    
    Memory: O(n) instead of O(n * 2^n)
    """
    count = 0
    for subset in power_set_generator(elements):
        if sum(subset) == target:
            count += 1
    return count
 
 
# Process 20 elements: 2^20 = 1M subsets
# Without generator: ~20MB of subset storage
# With generator: ~200 bytes for current subset
print(count_subsets_with_sum(list(range(10)), 25))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

                        {a, b, c}
                       /    |    \
                      /     |     \
                   {a,b}  {a,c}  {b,c}
                    /\     /\     /\
                   /  \   /  \   /  \
                  /    \ /    \ /    \
                {a}    {b}    {c}
                  \     |     /
                   \    |    /
                    \   |   /
                        ∅
 
Levels (by cardinality):
- Level 0: {} (1 element)
- Level 1: {a}, {b}, {c} (3 elements)
- Level 2: {a,b}, {a,c}, {b,c} (3 elements)
- Level 3: {a,b,c} (1 element)
 
Lines connect subsets that differ by exactly one element (cover relation).

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
33

from itertools import combinations
 
def power_set_by_levels(elements):
    """
    Generate power set organized by subset cardinality.
    
    Returns a list of levels, where level k contains all subsets of size k.
    
    Useful when processing subsets by size (e.g., try smaller subsets first).
    """
    elements = list(elements)
    n = len(elements)
    
    levels = []
    for k in range(n + 1):  # k = 0, 1, 2, ..., n
        level_k = list(combinations(elements, k))
        levels.append([list(combo) for combo in level_k])
    
    return levels
 
 
# Example
levels = power_set_by_levels(['a', 'b', 'c'])
for level_num, level in enumerate(levels):
    print(f"Level {level_num} (size {level_num}): {level}")
 
# Output:
# Level 0 (size 0): [[]]
# Level 1 (size 1): [['a'], ['b'], ['c']]
# Level 2 (size 2): [['a', 'b'], ['a', 'c'], ['b', 'c']]
# Level 3 (size 3): [['a', 'b', 'c']]
 
# Total subsets: C(3,0) + C(3,1) + C(3,2) + C(3,3) = 1 + 3 + 3 + 1 = 8 ✓

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

def subset_to_mask(subset, elements):
    """Convert a subset to its bitmask representation."""
    element_to_index = {e: i for i, e in enumerate(elements)}
    mask = 0
    for elem in subset:
        mask |= (1 << element_to_index[elem])
    return mask
 
 
def mask_to_subset(mask, elements):
    """Convert a bitmask to its subset representation."""
    return [elements[i] for i in range(len(elements)) if mask & (1 << i)]
 
 
def subset_union(mask_a, mask_b):
    """Union of two subsets via bitwise OR."""
    return mask_a | mask_b
 
 
def subset_intersection(mask_a, mask_b):
    """Intersection of two subsets via bitwise AND."""
    return mask_a & mask_b
 
 
def subset_complement(mask, n):
    """Complement of a subset (flip all n bits)."""
    full_mask = (1 << n) - 1  # All 1s: 111...1
    return mask ^ full_mask
 
 
def is_subset(mask_a, mask_b):
    """Check if subset A ⊆ subset B."""
    return (mask_a & mask_b) == mask_a
 
 
# Example usage
elements = ['a', 'b', 'c']
 
set_a = subset_to_mask({'a', 'b'}, elements)  # 011 = 3
set_b = subset_to_mask({'b', 'c'}, elements)  # 110 = 6
 
union = subset_union(set_a, set_b)  # 011 | 110 = 111 = 7
print(f"Union: {mask_to_subset(union, elements)}")  # ['a', 'b', 'c']
 
intersection = subset_intersection(set_a, set_b)  # 011 & 110 = 010 = 2
print(f"Intersection: {mask_to_subset(intersection, elements)}")  # ['b']
 
complement_a = subset_complement(set_a, 3)  # 011 ^ 111 = 100 = 4
print(f"Complement of {mask_to_subset(set_a, elements)}: {mask_to_subset(complement_a, elements)}")  # ['c']

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

def power_set_gray_code(elements):
    """
    Generate power set in Gray code order.
    
    Each consecutive subset differs by exactly one element.
    """
    elements = list(elements)
    n = len(elements)
    subsets = []
    
    for i in range(1 << n):
        gray = i ^ (i >> 1)  # Convert to Gray code
        subset = [elements[j] for j in range(n) if gray & (1 << j)]
        subsets.append(subset)
    
    return subsets
 
 
def verify_gray_code_property(subsets):
    """Verify that each consecutive pair differs by one element."""
    for i in range(len(subsets) - 1):
        set_a = set(subsets[i])
        set_b = set(subsets[i + 1])
        sym_diff = set_a ^ set_b  # Symmetric difference
        if len(sym_diff) != 1:
            return False, i
    return True, -1
 
 
# Demonstration
elements = [1, 2, 3]
gray_subsets = power_set_gray_code(elements)
 
print("Gray code ordered subsets:")
for i, s in enumerate(gray_subsets):
    print(f"  {i}: {s}")
 
is_valid, error_idx = verify_gray_code_property(gray_subsets)
print(f"
Gray code property verified: {is_valid}")
 
# Output:
# Gray code ordered subsets:
#   0: []
#   1: [1]
#   2: [1, 2]
#   3: [2]
#   4: [2, 3]
#   5: [1, 2, 3]   -- wait, differs by adding 1 and 3? Let me check...
# Actually: Gray code for i=5 is 5^2 = 7 = 111, so [1,2,3]
# Gray code for i=4 is 4^2 = 6 = 110, so [2,3]
# Diff: {1} added ✓

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/**
 * Generate power set using backtracking.
 * @param {Array} elements - Input elements
 * @returns {Array} Array of all subsets
 */
function powerSet(elements) {
    const result = [];
    
    function backtrack(index, current) {
        if (index === elements.length) {
            result.push([...current]); // Spread operator for shallow copy
            return;
        }
        
        // Exclude
        backtrack(index + 1, current);
        
        // Include
        current.push(elements[index]);
        backtrack(index + 1, current);
        current.pop();
    }
    
    backtrack(0, []);
    return result;
}
 
/**
 * Generator version for memory efficiency.
 */
function* powerSetGenerator(elements) {
    const n = elements.length;
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset.push(elements[i]);
            }
        }
        yield subset;
    }
}
 
// Usage
const elements = ['a', 'b', 'c'];
console.log(powerSet(elements));
 
for (const subset of powerSetGenerator(elements)) {
    console.log(subset);
}

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

function powerSet<T>(elements: T[]): T[][] {
    const result: T[][] = [];
    
    function backtrack(index: number, current: T[]): void {
        if (index === elements.length) {
            result.push([...current]);
            return;
        }
        
        backtrack(index + 1, current);
        current.push(elements[index]);
        backtrack(index + 1, current);
        current.pop();
    }
    
    backtrack(0, []);
    return result;
}
 
// Generator version
function* powerSetGen<T>(elements: T[]): Generator<T[], void, unknown> {
    const n = elements.length;
    for (let mask = 0; mask < (1 << n); mask++) {
        yield elements.filter((_, i) => mask & (1 << i));
    }
}
 
// Usage with type inference
const numbers: number[] = [1, 2, 3];
const subsets: number[][] = powerSet(numbers);

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import java.util.*;
 
public class PowerSet {
    public static <T> List<List<T>> powerSet(List<T> elements) {
        List<List<T>> result = new ArrayList<>();
        backtrack(elements, 0, new ArrayList<>(), result);
        return result;
    }
    
    private static <T> void backtrack(
            List<T> elements, 
            int index, 
            List<T> current, 
            List<List<T>> result) {
        
        if (index == elements.size()) {
            result.add(new ArrayList<>(current)); // Create copy
            return;
        }
        
        // Exclude
        backtrack(elements, index + 1, current, result);
        
        // Include
        current.add(elements.get(index));
        backtrack(elements, index + 1, current, result);
        current.remove(current.size() - 1);
    }
    
    // Bit manipulation version
    public static <T> List<List<T>> powerSetBit(List<T> elements) {
        List<List<T>> result = new ArrayList<>();
        int n = elements.size();
        
        for (int mask = 0; mask < (1 << n); mask++) {
            List<T> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(elements.get(i));
                }
            }
            result.add(subset);
        }
        
        return result;
    }
}