Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: One Zero variants_without_repetition

by Limbic~Region (Chancellor)
on Aug 07, 2007 at 12:26 UTC ( [id://631029]=note: print w/replies, xml ) Need Help??


in reply to One Zero variants_without_repetition

thenetfreaker,
You want permutations not combinations. With a combination, order does not matter and it obviously does to you. While I have written my own iterator, I think tye's Permuting with duplicates and no memory would be perfect for you.

Cheers - L~R

Replies are listed 'Best First'.
Re^2: One Zero variants_without_repetition (Al gor loops)
by tye (Sage) on Aug 07, 2007 at 15:14 UTC

    ... which is available as Algorithm::Loops::NextPermute().

    And Algorithm::Loops offers another way to do this as well.

    use strict; use Algorithm::Loops qw( NestedLoops ); my $bits= 8; my $ones= 5; my $iter= NestedLoops( [ [ 0 .. $bits-1 ], ( sub { [ 1+$_[-1] .. $bits-1 ] } ) x ($ones-1), ], ); my @ones; while( @ones= $iter->() ) { my @bits= (0) x $bits; @bits[@ones]= (1) x $ones; print join '', @bits, $/; }

    Which is like

    my $bits= 8; for my $o0 ( 0 .. $bits-1 ) { for my $o1 ( 1+$o0 .. $bits-1 ) { for my $o2 ( 1+$o1 .. $bits-1 ) { for my $o3 ( 1+$o2 .. $bits-1 ) { for my $o4 ( 1+$o3 .. $bits-1 ) { my @bits= (0) x $bits; @bits[$o0,$o1,$o2,$o3,$o4]= (1)x5; } } } } }

    Except that the number of ones (and thus the number of nested loops) isn't hard-coded.

    Update: You can also avoid some looping at the tail end by setting tight top limits:

    use strict; use Algorithm::Loops qw( NestedLoops ); my $bits= 8; my $ones= 5; my $iter= NestedLoops( [ [ 0 .. $bits - $ones ], map( { # Need lexical for closure my $top= $bits - $ones + $_; sub { [ 1+$_[-1] .. $top ] } } 1 .. $ones-1, ), ], ); my @ones; while( @ones= $iter->() ) { my @bits= (0) x $bits; @bits[@ones]= (1) x $ones; print join '', @bits, $/; }

    - tye        

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://631029]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (4)
As of 2024-03-28 13:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found