in reply to Recursion problem

In essence this problem requires that you generate the subsets of the original set. Say you have the set (1,2,3,4). You want to find all these subsets 

1
1 2
1 3
1 4 
1 2 3
1 2 4
1 3 4
1 2 3 4
2
2 3
2 4
2 3 4
3
3 4
4

[download]
One neat way to get all the combinations is to use a binary approach where the presence of absence of a binary 1 is used to represent "grab this element" from the set. The number of possible combinations is (2**n)-1. It is easier to see in code: 
my @list = (1,2,3,4);
my $n = 2**@list -1;
for $b(1..$n) {
    printf "%2d: %04b ", $b, $b;
    my $i = $b;
    for (@list) {
        print "$_ " if $i%2;
        $i >>= 1;
        
    }
    print "\n";
}
__DATA__
 1: 0001 1    (get element 0)
 2: 0010 2    (get element 1)
 3: 0011 1 2  (get elements 0 and 1)
 4: 0100 3    (get element 2)
 5: 0101 1 3  (etc)
 6: 0110 2 3 
 7: 0111 1 2 3 
 8: 1000 4 
 9: 1001 1 4 
10: 1010 2 4 
11: 1011 1 2 4 
12: 1100 3 4 
13: 1101 1 3 4 
14: 1110 2 3 4 
15: 1111 1 2 3 4

[download]

Replies are listed 'Best First'.
Re^2: Recursion problem
by psini (Deacon) on May 25, 2008 at 14:53 UTC

    Yes it works, as long as your list is short.

    If the list can be longer than your integer precision, you should use big integers and I think this is overkill: there are situations in which recursion is useless and more time consuming than an iterative algorithm (I'm thinking of the classical book example of calculating n!) but in others it can be the fastest/cleanest approach

    Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.

[reply]
      psini,
      Yes it works, as long as your list is short.

      Finding all possible subsets of a set is called the powerset. The number of subsets is 2 ** N - 1 where N is the number of items in the original set and the - 1 is because we do not need to consider the empty set. The number of combinations does not change regardless of what approach you use - iteration or recursion.

      If the list can be longer than your integer precision, you should use big integers and I think this is overkill: there are situations in which recursion is useless and more time consuming than an iterative algorithm (I'm thinking of the classical book example of calculating n!) but in others it can be the fastest/cleanest approach

      Assume the list has 20 items. That means 1,048,575 different subsets that need to be checked. Which is cleaner/faster - a single sub of about 5 lines that counts to 1,048,575 or invoking a sub a minimum of 1,048,575 times (memoization)?

      Personally, I finder it harder to think in terms of recursion than iteration. There are certainly examples where a recursive solution makes more sense (Towers of Hanoi and DFS come to mind) but in this case, I still think the iterative solution is better. Have you ever tried to do a BFS using recursion - my attempts have been ugly at best.

      Cheers - L~R

[reply]

        Ok Limbic~Region I tried hard, but I can't find anything against your point.

        I'm probably biased toward the recursive approach in general, but I've to admit that in this case (and probably many other I never thought of) an iterative solution is better. I promise I'll treasure this lesson and keep my mind open in the iteration vs. recursion issue

        Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.

[reply]

In Section Seekers of Perl Wisdom