Re^3: Finding all Combinations

[roboticus]

Limbic~Region:

I've finally got it! Thanks for the help you posted on your scratchpad. After a few hours of study, it finally paid off. I've commented it to describe how it works, and made a few changes to fix a minor bug, and remove some code that is never executed, and removed a state variable:

#------------------------------------------------------------
# Return an iterator of all possible combinations (of all
# lengths) of a set of symbols with the constraint that each
# symbol in each result is less than the symbol to its right.
#
sub combo {

    # The symbols we draw our results from:
    my @list = @_;

    # The trivial case
    return sub { ( ) } if ! @_;

    # Persistent state for the closure
    my (@position, # Last set of symbol indices generated
        @stop);    # Last set possible for $by symbols

    # Start by telling iterator that it just finished
    # (next=1) all results of 0 digits.
    my ($by, $next) = (0, 1);

    return sub {

        # We're done after we've returned a list of all symbols
        return () if @position == @list;

        if ( $next ) {
            # We finished all combos of size $by, now do $by+1
            $by++;

            # If new size is larger than list, we're done!
            return () if $by > @list;

            # Start with leftmost $by symbols (except last,
            # which is preincremented before use)
            @position = (0 .. $by - 2, $by - 2);

            # Our stop condition is when we've returned the
            # rightmost $by symbols
            @stop = @list - $by .. $#list;

            $next = undef;
        }

        # Start by trying to advance the rightmost digit
        my $cur = $#position;
        {   # **** redo comes back here! ****

            # Advance current digit to next symbol
            if ( ++$position[ $cur ] > $stop[ $cur ] ) {

                # Keep trying next-most rightmost digit
                # until we find one that's not 'stopped'
                $position[ --$cur ]++;
                redo if $position[ $cur ] > $stop[ $cur ];

                # Reset digits to right of current digit to
                # the leftmost possible positions
                my $new_pos = $position[ $cur ];
                @position[$cur .. $#position] = $new_pos .. $new_pos+$
+by;
            }
        }

        # Advance to next result size when we return last
        # possible result of this size
        $next = $position[0]==$stop[0];

        return @list[ @position ];
    }
}

Thanks again! I learned a lot from this exercise.

UPDATE: I just tweaked the code a bit to make it check for done less frequently so it'll run a bit quicker. It munges up the code listing a bit though. Is there a better way to edit the code so it's obvious without interspersing download links?

--roboticus

[Limbic~Region]

roboticus,
I am glad that you were able to decipher given my description of how the algorithm works. I am interested in knowing what was the minor bug and what code was never executed? If you found this interesting, might I suggest you move on to How A Function Becomes Higher Order and my iterator tutorial.

[roboticus]

Limbic~Region:

The minor bug is that this statement:

    $position[0] == @list ? $done = 1 : $next = 1;

never sets the $done flag. I think you meant:

    @position == @list ? $done = 1 : $next = 1;

And because $done is never set,

        return () if $done;

never executes. It's a truly minor bug though, because you have another bit of code that detects the end condition:

            return () if $by > @list;

So I just removed $done entirely. (Actually, looking at my code, when I was rearranging, I removed that last condition. I should've kept it because my code tests for the end condition on every call, where your terminator checks only when it's time to go to the next size of results. I'll update my node to reflect that.)

The other thing I did was remove $end_pos since its value has such a limited lifetime, and add a passel of comments so I wouldn't forget how it works!

Now off to How A Function Becomes Higher Order and yer iterator toot!

--roboticus

[Limbic~Region]

roboticus,
That's not in the bug in the sense that it results in incorrect behavior. Minor quibble aside - you are right that it does not belong. It's left over from a previous revisions. The original version I had was much closer to blokhead's code which does not precalulate stop values and ends up spinning cycles doing math every iteration. Next I reversed the array so the index could be used to determine stop value with less math. This was unfortunate because I still had to do some math and reverse the return. Finally, I realized I could precalulate the stop values but didn't do a good job of cleaning up my false starts.

Thanks for the analysis - glad to have been some help.