javarecursionpowerset

Powerset of a list with equal elements in Java


Chat-GPT generated me the following code in Java, but it still doesn't work with equal elements.

The supposed output is incorrect, since the equal elements get simply ignored and I can't figure out why.

import java.util.*;

public class PowerSetWithEqualElements {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 2);
        Set<Set<Integer>> powerSet = generatePowerSet(list);
        System.out.println(powerSet);
    }

    public static <T> Set<Set<T>> generatePowerSet(List<T> list) {
        Set<Set<T>> powerSet = new HashSet<>();
        generatePowerSet(list, 0, new HashSet<>(), powerSet);
        return powerSet;
    }

    private static <T> void generatePowerSet(List<T> list, int index, Set<T> currentSet, Set<Set<T>> powerSet) {
        if (index == list.size()) {
            powerSet.add(new HashSet<>(currentSet));
            return;
        }
        // Exclude the current element
        generatePowerSet(list, index + 1, currentSet, powerSet);
        // Include the current element
        currentSet.add(list.get(index));
        generatePowerSet(list, index + 1, currentSet, powerSet);
        currentSet.remove(list.get(index));
        // Skip duplicate elements
        while (index + 1 < list.size() && list.get(index) == list.get(index + 1)) {
            index++;
        }
        generatePowerSet(list, index + 1, currentSet, powerSet);
    }
}

This code will output:

[[], [1], [1, 2], [2]]

The supposed output is:

[[], [1], [1, 2], [2], [2, 2], [1, 2, 2]]

Solution

  • I would recomend to use a library for such kind of tasks which offer a pre-built, tested, and optimized functionality instead of coding it yourself; unless it is for learning resons. There is for example combinatoricslib3 a simple to use java library to deal with permutations, combinations, subsets, powersets .... With Combinatorics lib your code could look like

    import java.util.Arrays;
    import java.util.List;
    
    import org.paukov.combinatorics3.Generator;
    
    public class Example {
        public static void main(String args[]) {
            List<Integer> list = Arrays.asList(1, 2, 2);
            Generator.subset(list)
                     .simple()
                     .stream()
                     .forEach(System.out::println);
        }
    }
    

    to produce the output:

    []
    [1]
    [2]
    [1, 2]
    [2]
    [1, 2]
    [2, 2]
    [1, 2, 2]