Geek Answers Handbook

Best recursive algorithm for printing subsets

I am trying to find a good recursive algorithm for printing 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 tried a lot of things, but this does not work. There are all examples of set algorithms on the Internet, but I want to write my own for training purposes.

Can anyone help me with this?

Yours faithfully,

0
source share
3 answers

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); }
+1
source

To build a recursive algorithm, you may notice that each subset of length 3 of {1,2,3,4,5} is either:

  • Contains the element "1" and 2 elements from {2,3,4,5}.
  • Does not contain the element "1" and 3 elements from {2,3,4,5}.

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

+1
source

I had a very similar problem a couple of years ago. how I eventually implemented this:

1. Store each set as a sorted array of element identifiers (no two identifiers are the same)

2. for iterating over subsets of a given size, N begin with 1 N elements of the original set

3. To move on to the next subset, you implement a kind of “clockwork” mechanism - take the last (highest identifier) ​​of your subset and replace it with your neighbor in the subset (next higher identifier).

4. If the superset does not have such a higher neighbor, increase the next lower element of the subset, and then set the oldest memeber next for it.

steps 3 and 4 are recursive.

An example of a sequence of results for iterating over all triplets {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}

etc.

more complex than brand offer, but takes up less memory space and stack. its also “restartable” - this means that you can pass some subset to algo and it will be your “next” subset.

+1
source

More articles:


All Articles