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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of