How to generate a power set of a given set?

by

Power set of a set A is the set of all of the subsets of A.

Not the most friendly definition in the world, but an example will help :

Eg. for {1, 2}, the subsets are : {}, {1}, {2}, {1, 2}

Thus, the power set is {{}, {1}, {2}, {1, 2}}

To generate the power set, observe how you create a subset : you go to each element one by one, and then either retain it or ignore it.

Let this decision be indicated by a bit (1/0).

Thus, to generate {1}, you will pick 1 and drop 2 (10).

On similar lines, you can write a bit vector for all the subsets :

  • {} -> 00
    {1} -> 10
    {2} -> 01
    {1,2} -> 11

To reiterate : A subset if formed by including some or all of the elements of the original set. Thus, to create a subset, you go to each element, and then decide whether to keep it or drop it. This means that for each element, you have 2 decisions. Thus, for a set, you can end up with 2^N different decisions, corresponding to 2^N different subsets.

See if you can pick it up from here.

More Related Contents:

  1. Calculate distance between two latitude-longitude points? (Haversine formula)
  2. Unique (non-repeating) random numbers in O(1)?
  3. How to determine if a point is in a 2D triangle? [closed]
  4. How do I calculate a point on a circle’s circumference?
  5. Algorithm to find Largest prime factor of a number
  6. Fast permutation -> number -> permutation mapping algorithms
  7. Algorithm to detect intersection of two rectangles?
  8. How to make rounded percentages add up to 100%
  9. Writing your own square root function
  10. Sort points in clockwise order?
  11. How do you calculate the average of a set of circular data? [closed]
  12. Precise subpixel line drawing algorithm (rasterization algorithm)
  13. Finding out nth fibonacci number for very large ‘n’
  14. Algorithm for finding similar images
  15. Why does this simple shuffle algorithm produce biased results?
  16. Computing set intersection in linear time?
  17. Floating Point Divider Hardware Implementation Details
  18. Unsupervised clustering with unknown number of clusters
  19. Circle-circle intersection points
  20. How to find the smallest number with just 0 and 1 which is divided by a given number?
  21. How to calculate the index (lexicographical order) when the combination is given
  22. How do I find a factorial? [closed]
  23. Calculating the position of points in a circle
  24. Strategies for simplifying math expressions
  25. How to express tetration function, for complex numbers
  26. What is the method for converting radians to degrees?
  27. How to check if an integer is a power of 3?
  28. determine if a point sits inside an arbitrary shape?
  29. How can I perform Collision Detection on rotated rectangles? [closed]
  30. Location of highest density on a sphere

Leave a Comment