# finding every combination of n values at y positions

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

1. ### Steve (another one)Guest

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

2. ### Paul LalliGuest

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

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:ermute). One does not
(List:ermutor):
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

3. ### John W. KrahnGuest

"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
4. ### Steve (another one)Guest

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
5. ### Anno SiegelGuest

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