Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time.

Given a set of numbers (say, {1, 4, 5, 9}), I want to enumerate all subsets of this set (its power set, really) in a certain order: increasing sum of the elements.

For example, given {1, 4, 5, 9}, the subsets should be enumerated in this order, "smaller" sets first:

{} = 0

{1} = 1

{4} = 4

{5} = 5

{1, 4} = 5

{1, 5} = 6

{9} = 9

{4, 5} = 9

{1, 9} = 10

{1, 4, 5} = 10

{4, 9} = 13

{5, 9} = 14

{1, 4, 9} = 14

{1, 5, 9} = 15

{4, 5, 9} = 18

{1, 4, 5, 9} = 19

This feels like some unholy mix between a breadth-first search and a depth-first search, but I can't wrap my head around the proper way to mix these two search strategies.

My search space is very large ($2^{64}$ elements) so I can't precompute them all up-front and sort them. On that note, I also don't need to enumerate the entire search space -- the smallest 4,096 subsets is fine, for example.

Can anyone give any pointers or even any clues to google for? Many thanks.

share|improve this question
    
Do you need to iterate over these sets in this order, or do you need a 1-1 map from the sets to integers. In other words do you want "foreach set do { ... }" to get the sets in a particular order, or do you want "for the 47th set do this" and "which number is this set?" –  Jack Schmidt Dec 7 '11 at 23:19
    
Finding each subset's number is trivial -- just sum them up. Consider, purely for example, guessing the bits of a password where each bit has a confidence score that lets you know how likely you got it right. You'd want to try the passwords with the smallest total penalty scores first. Similarly, I want to search through this huge space, trying sets with the smallest penalty first. The sets themselves are used for something else at each step--this algorithm would merely describe which order to try each subset. –  Michael Dec 8 '11 at 0:05
add comment

2 Answers 2

up vote 4 down vote accepted

Here's an algorithm. The basic idea is that each number in the original set iterates through the list of subsets you've already found, trying to see if adding that number to the subset it's currently considering results in the smallest subset sum not yet found.

The algorithm uses four arrays (all of which are indexed starting with $0$).

  1. $N$ consists of the numbers in the original set; i.e., $N = [1, 4, 5, 9]$ in your example.
  2. $L$ is the list of subsets found so far.
  3. $A[i]$ contains the subset that $N[i]$ is currently considering.
  4. $S[i]$ is the sum of the elements of subset $i$ in $L$.

Algorithm:

  1. Initialize $N$ to numbers in the original set, all entries of $A$ to $0$, $L[0] = \{\}$, $S[0] = 0$. Let $j = 1$.
  2. For iteration $j$ find the minimum of $S[A[i]] + N[i]$ over all numbers $N[i]$ in the original set. (This finds the subset with smallest sum not yet in $L$.) Tie-breaking is done by number of elements in the set. Let $i^*$ denote the argmin.
  3. Let $L[j] = L[A[i^*]] \cup \{N[i^*]\}$. Let $S[j] = S[A[i^*]] + N[i^*]$. (This updates $L$ and $S$ with the new subset.)
  4. Increase $A[i^*]$ to the next item in $L$ that has no number larger than $N[i^*]$. If there is none, let $A[i^*] =$ NULL. (This finds the next subset in $L$ to consider for the number $N[i^*]$ just added to an existing subset in $L$ to create the subset just added to $L$.)
  5. If all entries in $A[i]$ are NULL, then stop, else increment $j$ and go to Step 2.


For example, here are the iterations for your example set, together with the subset in $L$ currently pointed to by each number.

Initialization:     
{}   1, 4, 5, 9

Iteration 1:    
{}   4, 5, 9
{1}  

Iteration 2:  
{}   5, 9
{1}  4 
{4}

Iteration 3:  
{}   9
{1}  4, 5
{4}
{5}

Iteration 4:  
{}   9
{1}  5
{4}
{5}
{1,4}

Iteration 5:  
{}   9
{1}  
{4}  5
{5}
{1,4}
{1,5}

Iteration 6:  
{}   
{1}  9
{4}  5
{5}
{1,4}
{1,5}
{9}

Iteration 7:  
{}   
{1}    9
{4}  
{5}
{1,4}  5
{1,5}
{9}
{4,5}

Iteration 8:  
{}   
{1}    
{4}    9
{5}
{1,4}  5
{1,5}
{9}
{4,5}
{1,9}

Iteration 9:  
{}   
{1}    
{4}    9
{5}
{1,4}  
{1,5}
{9}
{4,5}
{1,9}
{1,4,5}

And the rest of the iterations just involve adding $9$ successively to each subset already constructed that doesn't include $9$.

share|improve this answer
1  
My goodness, that's amazing. How did you come up with this? I would never have thought to think of the problem this way. Many thanks for your help. –  Michael Dec 8 '11 at 23:05
    
@Michael: I just tried to exploit the idea that any set appearing in the list had to consist of its largest element added to some set that had already appeared in the list. And you're welcome; it was a fun problem to think about. :) –  Mike Spivey Dec 8 '11 at 23:14
add comment

(Too long for a comment.)

Nijenhuis and Wilf's Combinatorial Algorithms details an algorithm for enumerating all the subsets of a given set, based on the Gray code (there is also a modification that makes it produce the subsets lexicographically). The book can be downloaded for free from the link I gave. You can download the FORTRAN routines NEXSUB() and LEXSUB() from Skiena's webpage. Some modification would be needed to have it output results in your desired order.

share|improve this answer
    
Thank you, I'll look into this. –  Michael Dec 8 '11 at 0:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.