This week's book giveaway is in the Web Services forum.
We're giving away four copies of Microservices in Action and have Morgan Bruce & Paulo A. Pereira on-line!
See this thread for details.
Win a copy of Microservices in Action this week in the Web Services forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Powerset algorithm  RSS feed

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi.

I need help writing a program that will print the powerset of a set/array. I basically just need the idea/algorithm of how to print it. If I knew where to start I'm certain I could code it.

Could someone please point me in the right direction?
 
author and iconoclast
Posts: 24203
40
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

Welcome to JavaRanch!

Let's say there are N elements in the set. The powerset of a set contains 2^N elements, so a 32-element set gives rise to a 4-billion element powerset.

Now imagine an N-bit integer. Let each bit in the number represent one specific element e in the original set. There is one element E in the powerset for each value this integer can take. For each value of the integer, the 1-bits correspond to the elements e of the original set that belong to this powerset element E, and the 0-bits corresponds to elements not in E.

So to print the powerset, you use either a real integer or long, or an array of booleans or any other representation you like of an integer. Then you "count", one value at a time, and for each value of the integer, you compute the corresponding element E of the powerset and print it.
 
Tyler Long
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Originally posted by Ernest Friedman-Hill:
Hi,

Welcome to JavaRanch!

Let's say there are N elements in the set. The powerset of a set contains 2^N elements, so a 32-element set gives rise to a 4-billion element powerset.

Now imagine an N-bit integer. Let each bit in the number represent one specific element e in the original set. There is one element E in the powerset for each value this integer can take. For each value of the integer, the 1-bits correspond to the elements e of the original set that belong to this powerset element E, and the 0-bits corresponds to elements not in E.

So to print the powerset, you use either a real integer or long, or an array of booleans or any other representation you like of an integer. Then you "count", one value at a time, and for each value of the integer, you compute the corresponding element E of the powerset and print it.



I do not understand this.
Thanks for the help anyway.
 
Ranch Hand
Posts: 212
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you understand what a power set is?
 
lowercase baba
Posts: 12628
50
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
what Ernest is saying is that you can use the bits in an integer (or long) as "flags" for whether or not to include an element. say you have 3 elements.

2 ^ 3 = 8.

so, you need to count from 0 - 7 (giving you the 8 powerset elements).

as you count, you look at which bits in your counter are on. so when you get to say 3, your counter looks like this:

000000...000011 (the exact number of 0's depends on your use of an int vs. a long, but it doesn't matter).

so, from this, you know to include the 1st and the 2nd elements of the original set ( the set called e) as the elements of one of your powerset (E elements.
 
Tyler Long
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is this right? And I do this up until 16? 2^4?

Let's say I had the set {Grapes, Apples, Oranges, Pears}.

0001 {Grapes}

0010 {Apples}

0011 {Grapes, Apples}

0100 {Oranges}

0101 {Grapes, Oranges}

0110 {Apples, Oranges}

0111 {Grapes, Apples, Oranges}

1000 {Pears}
 
Ernest Friedman-Hill
author and iconoclast
Posts: 24203
40
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, that's correct!
 
Tyler Long
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Originally posted by Ernest Friedman-Hill:
Yes, that's correct!



Thank you very much. I really appreciate your help.

You taught me something new.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!