Memory efficient power set algorithm

by

There is a trivial bijective mapping from the power set of X = {A,B,C,D,E,F,G,H,I} to the set of numbers between 0 and 2^|X| = 2^9:

Ø maps to 000000000 (base 2)

{A} maps to 100000000 (base 2)

{B} maps to 010000000 (base 2)

{C} maps to 001000000 (base 2)

…

{I} maps to 000000001 (base 2)

{A,B} maps to 110000000 (base 2)

{A,C} maps to 101000000 (base 2)

…

{A,B,C,D,E,F,G,H,I} maps to 111111111 (base 2)

You can use this observation to create the power set like this (pseudo-code):

Set powerset = new Set();
for(int i between 0 and 2^9)
{
  Set subset = new Set();
  for each enabled bit in i add the corresponding letter to subset
  add subset to powerset
}

In this way you avoid any recursion (and, depending on what you need the powerset for, you may even be able to “generate” the powerset without allocating many data structures – for example, if you just need to print out the power set).

More Related Contents:

  1. What is tail recursion?
  2. What is tail call optimization?
  3. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  4. How can I pair socks from a pile efficiently?
  5. Unique (non-repeating) random numbers in O(1)?
  6. How do I check if a number is a palindrome?
  7. Is there an O(n) integer sorting algorithm?
  8. Determine font color based on background color
  9. Nearest neighbors in high-dimensional data?
  10. What algorithm gives suggestions in a spell checker?
  11. How can I measure the similarity between two images? [closed]
  12. Algorithm to generate anagrams
  13. Generate all unique substrings for given string
  14. design a stack such that getMinimum( ) should be O(1)
  15. How to check if line segment intersects a rectangle?
  16. How to read values from numbers written as words?
  17. Calculate largest inscribed rectangle in a rotated rectangle
  18. Find the first un-repeated character in a string
  19. What is a bubble sort good for? [closed]
  20. Iterating over a Binary Tree with O(1) Auxiliary Space
  21. How do I find a factorial? [closed]
  22. Best way of calculating n choose k?
  23. Peak detection of measured signal
  24. “Rounding” colour values to the nearest of a small set of colours
  25. What algorithm can calculate the power set of a given set?
  26. Algorithm for permutations of operators and operands
  27. Convert light frequency to RGB?
  28. Tournament bracket placement algorithm
  29. How to generate a power set of a given set?
  30. Postfix notation to expression tree

Leave a Comment