finding every combination of n values at y positions

Discussion in 'Perl Misc' started by Steve (another one), Jul 2, 2004.

  1. I have just wasted a crazy amount of time trying to populate an array
    containing every combination of n values at y positions. It feels as
    though it should be trivial and the sort of thing I do every day, but in
    fact I could not find the simple solution that surely must exist.

    Below is my best attempt - it will also explain the task if I haven't
    been clear - can someone tell me if there is a simpler way of doing it.

    Thanks

    Steve

    (Actually I am probably really hoping you will all say "cool, what a
    brilliant way to do it", but I somehow doubt that will happen!)


    #!/usr/bin/perl

    ## find all possible combinations of values at $number_of_position positions

    use strict;

    my $min_value = 1;
    my $max_value = 4;
    my $number_of_positions = 3;


    my $individual = 0;
    my $incrementing = 0;
    my $dun;
    my @data_set;
    my @one_set;
    for my $x (0..($number_of_positions-1)){push @one_set,$min_value}

    ###################################################
    sub increment{
    if ($one_set[$incrementing] > $max_value){$incrementing++;
    $one_set[$incrementing]++;
    increment();
    $incrementing--;

    $one_set[$incrementing]=$min_value;
    }
    }
    ###################################################

    while (1){
    push @{$data_set[$individual]}, @one_set;

    # done yet ?
    foreach (@one_set){ $dun = ($_ == $max_value); last unless $dun}
    last if $dun;

    $one_set[$incrementing]++;
    $individual++;

    increment();
    }

    # show array
    $individual=0;
    foreach (@data_set){ print "$individual - @{$_}\n"; $individual++ }
     
    Steve (another one), Jul 2, 2004
    #1
    1. Advertising

  2. Steve (another one)

    Paul Lalli Guest

    On Fri, 2 Jul 2004, Steve (another one) wrote:

    > I have just wasted a crazy amount of time trying to populate an array
    > containing every combination of n values at y positions. It feels as
    > though it should be trivial and the sort of thing I do every day, but in
    > fact I could not find the simple solution that surely must exist.


    You might want to consult CPAN the next time you feel yourself spending a
    crazy amount of time doing anything in Perl. Chances are, someone's
    already done it.

    You might also want to check the FAQ, which could possibly tell you if
    someone's already done it, and if so, where to find their solution.

    In this case,

    perldoc -q permute

    shows you first a straight Perl solution, which it itself claims is "very
    inefficient". It then tells you about two modules on CPAN which are
    faster. One requires a C compiler (Algoritm::permute). One does not
    (List::permutor):
    http://search.cpan.org/~phoenix/List-Permutor-0.022/Permutor.pm

    Note that this doesn't do *exactly* what you wanted, but it's so similar,
    I'd think it'd be trivial to use or modify for your own goals.

    Paul Lalli
     
    Paul Lalli, Jul 2, 2004
    #2
    1. Advertising

  3. "Steve (another one)" wrote:
    >
    > I have just wasted a crazy amount of time trying to populate an array
    > containing every combination of n values at y positions. It feels as
    > though it should be trivial and the sort of thing I do every day, but in
    > fact I could not find the simple solution that surely must exist.
    >
    > Below is my best attempt - it will also explain the task if I haven't
    > been clear - can someone tell me if there is a simpler way of doing it.
    >
    > [snip]


    You could do it like this:

    #!/usr/bin/perl
    use warnings;
    use strict;

    my $min_value = 1;
    my $max_value = 4;
    my $number_of_positions = 3;

    my $glob = ( '{' . join( ',', $min_value .. $max_value ) . '}' ) x $number_of_positions;

    $individual = 0;
    print $individual++, " - @$_\n" for map [ /./g ], glob $glob;

    __END__


    :)

    John
    --
    use Perl;
    program
    fulfillment
     
    John W. Krahn, Jul 3, 2004
    #3
  4. John W. Krahn wrote:
    > "Steve (another one)" wrote:
    >
    >>I have just wasted a crazy amount of time trying to populate an array
    >>containing every combination of n values at y positions. It feels as
    >>though it should be trivial and the sort of thing I do every day, but in
    >>fact I could not find the simple solution that surely must exist.
    >>
    >>Below is my best attempt - it will also explain the task if I haven't
    >>been clear - can someone tell me if there is a simpler way of doing it.
    >>
    >>[snip]

    >
    >
    > You could do it like this:
    >
    > #!/usr/bin/perl
    > use warnings;
    > use strict;
    >
    > my $min_value = 1;
    > my $max_value = 4;
    > my $number_of_positions = 3;
    >
    > my $glob = ( '{' . join( ',', $min_value .. $max_value ) . '}' ) x $number_of_positions;
    >
    > $individual = 0;
    > print $individual++, " - @$_\n" for map [ /./g ], glob $glob;
    >
    > __END__
    >
    >
    > :)
    >
    > John

    cool, what a brilliant way to do it :)
     
    Steve (another one), Jul 5, 2004
    #4
  5. Steve (another one)

    Anno Siegel Guest

    Steve (another one) <> wrote in comp.lang.perl.misc:
    > John W. Krahn wrote:
    > > "Steve (another one)" wrote:
    > >
    > >>I have just wasted a crazy amount of time trying to populate an array
    > >>containing every combination of n values at y positions. It feels as
    > >>though it should be trivial and the sort of thing I do every day, but in
    > >>fact I could not find the simple solution that surely must exist.
    > >>
    > >>Below is my best attempt - it will also explain the task if I haven't
    > >>been clear - can someone tell me if there is a simpler way of doing it.
    > >>
    > >>[snip]

    > >
    > >
    > > You could do it like this:
    > >
    > > #!/usr/bin/perl
    > > use warnings;
    > > use strict;
    > >
    > > my $min_value = 1;
    > > my $max_value = 4;
    > > my $number_of_positions = 3;
    > >
    > > my $glob = ( '{' . join( ',', $min_value .. $max_value ) . '}' ) x

    > $number_of_positions;
    > >
    > > $individual = 0;
    > > print $individual++, " - @$_\n" for map [ /./g ], glob $glob;
    > >
    > > __END__
    > >
    > >
    > > :)
    > >
    > > John

    > cool, what a brilliant way to do it :)


    It can also be considered a counting problem.

    Consider the number system whose base is $base = $max_value - $min_value + 1.
    Enumerate all numbers with $number_of_positions digits in this system.
    (There will be $base**$number_of_positions such numbers.) Increment each
    digit individually by $min_value. That yields the required set of
    combinations.

    The glob is a clever hack that does the required counting. A more
    direct way is this:

    my @digits = ( $min_value) x $number_of_positions;
    my $individual = 0;
    while ( 1 ) {
    print $individual++, " - @digits\n";
    last unless grep $_ < $max_value, @digits;
    for ( reverse @digits ) { # increment with carry
    last if ++ $_ <= $max_value;
    $_ = $min_value;
    }
    }

    Anno
     
    Anno Siegel, Jul 5, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Knut Krueger
    Replies:
    2
    Views:
    473
    Knut Krueger
    May 21, 2007
  2. =?Utf-8?B?SXJ3YW5zeWFo?=
    Replies:
    4
    Views:
    2,502
    =?Utf-8?B?SXJ3YW5zeWFo?=
    Oct 30, 2007
  3. bwv549
    Replies:
    7
    Views:
    118
    Peña, Botp
    Jul 24, 2007
  4. Milo Thurston
    Replies:
    10
    Views:
    275
    Aldric Giacomoni
    Dec 18, 2009
  5. roger

    every combination of letters

    roger, Oct 9, 2003, in forum: Perl Misc
    Replies:
    3
    Views:
    166
    Peter A. Krupa
    Oct 13, 2003
Loading...

Share This Page