Generate Powerset of a Set in Java

Write a program to generate Powerset of a set in Java. A power set of a set S is the set of all possible subsets of S, including the empty set and S itself.

For example, for set {a, b, c}, the subsets are:

{} (empty set)
{a}
{b}
{c}
{a, b}
{a, c}
{b, c}
{a, b, c}

and hence the power set of S is {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

The simplest solution is to use the Guava library. The powerSet() method provided by the Sets class calculates all possible subsets of the specified set.

import com.google.common.collect.ImmutableSet;

import com.google.common.collect.Sets;

import java.util.Set;

// Generate power set of a set in Java

class Main

{

public static void main(String[] args)

{

// Input Set

Set<Integer> ints = ImmutableSet.of(1, 2, 3);

// Generate power set using Guava

Set<Set<Integer>> result = Sets.powerSet(ints);

// print results

result.forEach(System.out::println);

}

Download Code

Output:

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

Another approach to find Powerset is to generate all binary numbers between 0 and 2ⁿ-1, where n is the size of the specified set. For instance, for set {a, b, c}, we generate binary numbers from 0 to 2³-1, and for each number generated, the corresponding set can be found by considering set bits in the number, as shown below:

0 = 000 = {}
1 = 001 = {c}
2 = 010 = {b}
3 = 011 = {b, c}
4 = 100 = {a}
5 = 101 = {a, c}
6 = 110 = {a, b}
7 = 111 = {a, b, c}

import com.google.common.collect.ImmutableSet;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

// Generate power set of a set in Java

class Main

{

public static Set<Set<Integer>> powerSet(Set<Integer> ints)

{

// convert set to a list

List<Integer> S = new ArrayList<>(ints);

// `N` stores the total number of subsets

long N = (long) Math.pow(2, S.size());

// Set to store subsets

Set<Set<Integer>> result = new HashSet<>();

// generate each subset one by one

for (int i = 0; i < N; i++)

{

Set<Integer> set = new HashSet<>();

// check every bit of `i`

for (int j = 0; j < S.size(); j++)

{

// if j'th bit of `i` is set, add `S[j]` to the current set

if ((i & (1 << j)) != 0) {

set.add(S.get(j));

}

result.add(set);

}

return result;

}

public static void main(String[] args)

{

// Input Set

Set<Integer> ints = ImmutableSet.of(1, 2);

// Generate power set using Guava

Set<Set<Integer>> result = powerSet(ints);

// print results

for (Set<Integer> set: result) {

System.out.println(set);

}

Download Code

Output:

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

That’s all about generating the powerset of a Set in Java.

Reference: https://en.wikipedia.org/wiki/Power_set

Generate Powerset of a Set in Java

Share this: