15
$\begingroup$

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.

  • 0
    Finding each subset's number is trivial -- just sum them up. Consider, purely for e$x$ample, 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.2011-12-08

3 Answers 3

12

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$.

  • 0
    I implemented @MikeSpivey's answer in Python as another answer to OP's question.2018-06-15
5

(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.

  • 0
    Thank you, I'll look into this.2011-12-08
1

For anyone curious, I implemented Mike Spivey's answer in Python.

def get_next_combs(N, n=4):   A = [0]*len(N)   L = [set()]   S = [0]   j = 1   while any(elem is not None for elem in A):     i_star = np.argmin([S[A[i]] + N[i] if A[i] is not None else np.inf for i in range(0, len(N))])     comb = L[A[i_star]].union((N[i_star],))     L.append(comb)     yield comb     S.append(S[A[i_star]] + N[i_star])     i = A[i_star]     A[i_star] = None     for i_next in range(i+1, len(L)):       if N[i_star] > max(L[i_next]):         A[i_star] = i_next         break 

Should the give the following sample output:

>>> for comb in get_next_combs(range(1,6)): ...     print(sum(comb), comb) ...  1 {1} 2 {2} 3 {1, 2} 3 {3} 4 {1, 3} 4 {4} 5 {2, 3} 5 {1, 4} 5 {5} 6 {1, 2, 3} 6 {2, 4} 6 {1, 5} 7 {1, 2, 4} 7 {3, 4} 7 {2, 5} 8 {1, 3, 4} 8 {1, 2, 5} 8 {3, 5} 9 {2, 3, 4} 9 {1, 3, 5} 9 {4, 5} 10 {1, 2, 3, 4} 10 {2, 3, 5} 10 {1, 4, 5} 11 {1, 2, 3, 5} 11 {2, 4, 5} 12 {1, 2, 4, 5} 12 {3, 4, 5} 13 {1, 3, 4, 5} 14 {2, 3, 4, 5} 15 {1, 2, 3, 4, 5}