All possible number combinations in perl

[austinj]

I want to be able to define a number (n) and get a print of all possible combinations of the number 1..n

For example:

my $n = 2

OUTPUT: 1 , 2 , 12

my $n = 3

OUTPUT: 1 , 2 , 3 , 12 , 13 , 23 , 123

etc.

I've been trying to wrap my head around a clean way to do this but thought the monks may be able to come up with a good answer.

Thanks in advance,

Austin

[BrowserUk]

all possible combinations of the number 1..n

Algorithm::Combinatorics

use Algorithm::Combinatorics qw[ combinations ];;

for my $k ( 1 .. 3 ) { 
    my $i = combinations( [ 1..3 ], $k ); 
    print @$_ while defined( $_ = $i->next );
};;
1
2
3
1 2
1 3
2 3
1 2 3

[Corion]

See, for example, GetNextPermute in Algorithm::Loops.

In your concrete case, you can also code the solution yourself by realizing that each of your numbers is either in the result or not. You seem to consider 12 and 21 to be the same. This means that for generating the result, you can count from 0 to 2 ** $n and use the bits to indicate which number should be included for the current result.

As your problem suspiciously sounds like homework, I won't post any code. If you post the code you've written and explain where your code goes wrong, you will likely receive more help.

[austinj]

It's not homework, I'm actually trying to build several strings with the combinations that will be used by a seperate input file. Anyway the following code accomplishes what I want (since my largest n will be 5) but this cannot be the best way to do it. I can't use the module option shown below since we are unable to install modules that are no available companywide.

#!/usr/local/bin/perl-5.10.1 -w

use strict;

my $var = 5;
my @list = 1..$var;
my @combos;
foreach ( 0..($var-1) ){
    
    my @temp_array;
    
            push(@temp_array , "$list[$_]");
    if($list[$_+1]){push(@temp_array , "$list[$_]$list[$_+1]")}
    if($list[$_+2]){push(@temp_array , "$list[$_]$list[$_+1]$list[$_+2
+]")}
    if($list[$_+3]){push(@temp_array , "$list[$_]$list[$_+1]$list[$_+2
+]$list[$_+3]")}
    if($list[$_+4]){push(@temp_array , "$list[$_]$list[$_+1]$list[$_+2
+]$list[$_+3]$list[$_+4]")}
    
    push(@combos, @temp_array);

}

print "@combos\n";

prints: 1 12 123 1234 12345 2 23 234 2345 3 34 345 4 45 5

[BrowserUk]

That isn't all the combinations:

[0] Perl> for $k ( 1 .. 5 ) { $i = combinations( [ 1..5 ], $k ); print
+ @$_ while defined( $_ = $i->next ) };;
1
2
3
4
5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
1 2 3 4 5

It may be what you want, but if it is, then you aren't after combinations.

[rovf]

From your example, it doesn't look like you are interested in combinations (otherwise, 235 would be included in your result), but in complete subsequences of a sequence 1..n. Hence, if N equals 100, the subsequence 42 43 44 45 would be in your result set. Right?
In this case, you just need two nested loops (one for the lower bound of the subsequence, one for the upper bound). There are N*N of such subsequences.

[tye]

How you would get this from Algorithm::Loops would actually be different:

use Algorithm::Loops qw< NestedLoops >;
my $getList = NestedLoops( [ map [$_,''], 1..3 ] );
my $getStr = sub { join '', $getList->() };
my $subset;
while(  $subset = $getStr->()  ) {
    print ' ', $subset;
}
print $/;

# or, if you also want the empty subset:

$getList = NestedLoops( [ map ['',$_], 1..3 ] );
$subset = $getStr->();
do {
    print " ($subset)";
} while(  $subset = $getStr->()  );
print $/;
__END__
 123 12 13 1 23 2 3
 () (3) (2) (23) (1) (13) (12) (123)

[brx]

sub mklist {
    my $num = shift;
    return "1" if $num == 1;
    return ($num,(map {$_,$_.$num} mklist($num-1)));
}

print join "\n", mklist(5);
print "\n";
__END__
5
4
45
3
35
34
345
2
25
24
245
23
235
234
2345
1
15
14
145
13
135
134
1345
12
125
124
1245
123
1235
1234
12345

[AnomalousMonk]

Although it addresses partitioning rather than the specific problem of the OP, section 5.1.1 "Finding All Possible Partitions" of Dominus's freely downloadable (and highly recommended) Higher Order Perl discusses an iterative approach that could be adapted to the OPed problem.

[snape]

Doing Permutations and Combinations using: recursion

[Cristoforo]

What you are looking for is called a powerset, with 2^n subsets. A collection of all possible sets from n items. For 2^5 == 32 possible sets (including the empty set).

[brx]

perl -e 'for my $i (1 .. (2<<4)-1){(1&($i>>$_)) && print 1+$_," " for 
+0..4; print"\n"} '
1 
2 
1 2 
3 
1 3 
2 3 
1 2 3 
4 
1 4 
2 4 
1 2 4 
3 4 
1 3 4 
2 3 4 
1 2 3 4 
5 
1 5 
2 5 
1 2 5 
3 5 
1 3 5 
2 3 5 
1 2 3 5 
4 5 
1 4 5 
2 4 5 
1 2 4 5 
3 4 5 
1 3 4 5 
2 3 4 5 
1 2 3 4 5