finding every combination of n values at y positions

[Steve (another one)]

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++ }

 

[Paul Lalli]

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: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

 

[John W. Krahn]

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

 

[Steve (another one)]

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

 

[Anno Siegel]

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