Best recursive algorithm to print out subsets

Question

I'm trying to find a good recursive algorithm to print out the subsets of a set. For example

size 5: gives the set {1,2,3,4,5} and the subsets off length 3 gives this output:

{5,4,3}
{5,4,2}
{5,4,1}
{5,3,2}
{5,3,1}
{5,2,1}
{4,3,2}
{4,3,1}
{4,2,1}
{3,2,1}

I've tried many things but it doesn't work. On the internet all the examples are with sets algorithms but I want to write my own, for learning purposes.

Could someone help me with this?

Kind regards,

You can consider it a counting problem. You have a base-5 number system, and you're just counting up from the smallest to the largest values for a 3-digit number. — Hot Licks, Dec 19 '11 at 12:17
not really like a counting problem - since you cant have the same "digit" more than once in your 3-digit "number" — radai, Dec 19 '11 at 12:26
also, 2 numbers with the same didits but in a different order are the same — radai, Dec 19 '11 at 12:47

score 1 · Answer 1 · answered Dec 19 '11 at 12:16

To construct a recursive algorithm you can notice that each subset of length 3 from {1,2,3,4,5} either:

Contains the element "1" and 2 elements from {2,3,4,5}.
Doesn't contains the element "1" and 3 elements from {2,3,4,5}.

Each of these two cases can be implemented by calling your function recursively.

radai · Answer 2 · 2011-12-19T12:39:44.963

i had a very similar problem couple of years ago. the way i eventually implemented this:
1. store every set as a sorted array of member ids (no 2 ids are the same)
2. for iterating over subsets of a given size N start with the 1st N elements of the original set
3. to get to the next subset you implement a sort of "clockwork" mechanism - take the last (highest id) memeber of your subset and replace it with its neighbour in the superset (the next higher id).
4. if there's no such higher neighbour in the superset, increment the next lower member of the subset, and then set the original highest memeber to be the next one after that.

steps 3 and 4 are recursive.

example result sequence for iterating over all triplets of {1,2,3,4,5}:

{1,2,3} - 3 lowest memebers
{1,2,4} - "increment" 3 to 4
{1,2,5} - 4 to 5
{1,3,4} - couldnt "increment" 5, so incremented 2-->3 and picked then next one as 3rd
{1,3,5} - 4-->5
{1,4,5} - couldnt increment 5 ...
{2,3,4} - couldnt increment 5, couldnt increment 4, incremented 1-->2 
{2,3,5}

and so on

its more complex than mark's proposal, but takes up less memory and stack space. its also "restartable" - meaning you can pass any subset into the algo and it will get you the "next" subset.

score 1 · Accepted Answer · answered Dec 19 '11 at 22:18

1

Finally it works:

public static void Dvz(String s, int x, int y){
    int i;
    if(y > 0)
      for(i = x; i >= y; i--)
      Dvz(s+i, i-1, y-1);
    else
      System.out.println(s);

  }

answered Dec 19 '11 at 22:18

user1007522

7,858
17
69
113

Best recursive algorithm to print out subsets

3 Answers3

Linked