Generate Powerset of a Set in Java

Write a program to generate Powerset of a Set in Java. A power set of 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}}.

 


 

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

 

Download   Run 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 to 2n-1 where n is the size of the specified set. For instance, for set {a, b, c}, we generate binary numbers from 0 to 23-1 and for each number generated, the correspoding 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}

 

Download   Run Code

Output:

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

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

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of