Algorithm for finding combinations of an variable length subset within an arbitrary length set

Question

I'm trying to work out a method that would return a list of all combinations of a subset within a set.The method call would look something like getSubsets(7, 3) based on the image below, the returned output I need would be in the form and order of:

... and so on

The image below shows exactly how the counting order should go. I've been banging my head on this one for a day can't find a good solution. TIA.

set of 7 with all 3 length subsets

rici · Accepted Answer · 2015-04-08 19:34:03Z

1

To get the next subset after a given subset:

Find the largest element in the subset whose successor is not in the subset.
Remove that element and all larger elements in the subset.
Starting with the successor element, add successive elements until the subset is the correct size.

If step 1 fails, you have enumerated all possible subsets.

In C:

bool next_subset(int* subset, int n, int k) {
  // subset is a vector of k ints in the range [0, n)
  int i, j;
  for (i = k - 1, j = n - 1; subset[i] == j; --i, --j) {
    if (i == 0)
      return false; // No more subsets
  }
  for (j = subset[i] + 1; i < k ; ++i, ++j) {
    subset[i] = j;
  }
  return true;
}

edited Apr 8, 2015 at 19:34

answered Apr 8, 2015 at 19:21

rici

243k30 gold badges263 silver badges364 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Hal50000 Over a year ago

Forgive me but in the above function, how do I know which subset I'm passing to it?

rici Over a year ago

@Hal50000 You always pass the same vector, so each time you give it the one you got the previous time. At least, that's the simple way. In general, you give it a vector and it modifies it so that it is the next entry in lexicographical order. So the first subset is {0,...,k-1} (i.e. for(int i = 0;i<k;++i)subset[i] = i;) as in your diagram.

rici Over a year ago

@Hal50000: Except that I numbered the elements from 0 instead of 1 :) But I'm sure you can figure out how to adapt it.

BoLe · Accepted Answer · 2015-05-27 10:31:59Z

0

If you know m of getSubsets(n, m) in advance, the code is just nested for-looping; eg. in Mathematica:

With[{n = 7},
 Table[{i, j, k},
   {i, n - 2}, {j, i + 1, n - 1}, {k, j + 1, n}]]

This produces all 3-subsets in the order you want, with n a parameter. Of course, if m is anything else than 3, the code is useless, specific code is needed for specific m. This is why I favor the flexible approach from @rici which is valid for general m.

answered May 27, 2015 at 10:31

BoLe

1631 silver badge5 bronze badges

Collectives™ on Stack Overflow

Algorithm for finding combinations of an variable length subset within an arbitrary length set

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related