DEV Community

Discussion on: Build a PowerSet

Collapse
 
idanarye profile image
Idan Arye

A subset of a N-sized set can be represented with an N-bit binary number, where each bit determines whether or not the subset contains its corresponding member. By incrementing the binary representation we can easily iterate over all the possible subsets.

Here is a simple implementation:

    public static <T> Set<Set<T>> powerSet(Set<T> set) {
        // We need to have them ordered, to match the bits of the binary rep.
        ArrayList<T> values = new ArrayList<>(set);
        boolean[] binaryRep = new boolean[values.size()];

        Set<Set<T>> powerSet = new HashSet<>();

        while (true) {
            Set<T> subset = createSubset(binaryRep, values);
            powerSet.add(subset);
            if (increment(binaryRep)) {
                // Iterated over all the numbers.
                break;
            }
        }

        return powerSet;
    }

    private static <T> Set<T> createSubset(boolean[] binaryRep, List<T> values) {
        Set<T> subset = new HashSet<>();
        for (int i = 0; i < binaryRep.length; ++i) {
            if (binaryRep[i]) {
                subset.add(values.get(i));
            }
        }
        return subset;
    }

    private static boolean increment(boolean[] binaryRep) {
        for (int i = 0; i < binaryRep.length; ++i) {
            if (binaryRep[i]) {
                // Make the 1 bit a 0 and carry the 1.
                binaryRep[i] = false;
            } else {
                // Finally reached a 0 bit - set it to 1 and we are done.
                binaryRep[i] = true;
                return false;
            }
        }
        // All the bits were 1 and we turned them to 0 - that means we "overflowed".
        return true;
    }