go ahead... be a heretic PerlMonks

### Comment on

 Need Help??
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;
```
# 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

In reply to Re^3: Finding all Combinations by roboticus
in thread Finding all Combinations by narse

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (2)
As of 2017-08-20 23:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (317 votes). Check out past polls.

Notices?