Home > Archive > PERL Beginners > November 2007 > fixed list combinatorics
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
fixed list combinatorics
|
|
| Dan Klose 2007-11-28, 7:01 pm |
| Hi list,
I am having a bad day and would really like some help (the coffee hasn't).
I have a list that looks like:
my @list = (1,2,3,4);
I would like to generate all patterns that follow:
1
2
3
4
12
123
23
34
234
1234
The list can be of any length and the next number in the list must be the
current number +1 ( i am not working with numbers - i think it is easier to
explain this way).
How do I do this? I did look at the Combinatorics module however it does
not impose fixed ordering as far as I can see.
Thanks
| |
| Andrew Curry 2007-11-28, 7:01 pm |
| Not sure this exactly what you want but
use strict;
my ( @list, @comb );
@list = ( 1, 2, 3, 4 );
combinations( \@list, \@comb );
print join ( "\n", @comb );
sub combinations {
my ( $list, $comb ) = @_;
my ( $key, $i, $x, $line, @comb );
foreach my $key ( @{$list} ) {
$line = $key;
push ( @{$comb}, $line );
for ( my $i = $key ; $i <= $#list ; $i++ ) {
$line .= $list->[$i];
push ( @{$comb}, $line );
}
}
}
Runs and returns....
1
12
123
1234
2
23
234
3
34
4
-----Original Message-----
From: Dan Klose [mailto:perlmunky@googlemail.com]
Sent: 28 November 2007 14:32
To: beginners@perl.org
Subject: fixed list combinatorics
Hi list,
I am having a bad day and would really like some help (the coffee hasn't).
I have a list that looks like:
my @list = (1,2,3,4);
I would like to generate all patterns that follow:
1
2
3
4
12
123
23
34
234
1234
The list can be of any length and the next number in the list must be the
current number +1 ( i am not working with numbers - i think it is easier to
explain this way).
How do I do this? I did look at the Combinatorics module however it does
not impose fixed ordering as far as I can see.
Thanks
This e-mail is from the PA Group. For more information, see
www.thepagroup.com.
This e-mail may contain confidential information. Only the addressee is
permitted to read, copy, distribute or otherwise use this email or any
attachments. If you have received it in error, please contact the sender
immediately. Any opinion expressed in this e-mail is personal to the sender
and may not reflect the opinion of the PA Group.
Any e-mail reply to this address may be subject to interception or
monitoring for operational reasons or for lawful business practices.
| |
| Yitzle 2007-11-28, 7:01 pm |
| On Nov 28, 2007 9:32 AM, Dan Klose <perlmunky@googlemail.com> wrote:
> I did look at the Combinatorics module however it does
> not impose fixed ordering as far as I can see.
Yet the example seems to indicate that the order is followed...
| |
| Andrew Curry 2007-11-28, 7:01 pm |
| Or a better one for none numeric's would be : I think.....
use strict;
my ( @list, @comb );
@list = ( 'A', 'B', 'C', 'D' );
combinations( \@list, \@comb );
print join ( "\n", @comb );
sub combinations {
my ( $list, $comb ) = @_;
my ( $key, $i, $x, $line, @comb, $n );
$n = 1;
foreach my $key ( @{$list} ) {
$line = $key;
push ( @{$comb}, $line );
for ( my $i = $n ; $i <= $#list ; $i++ ) {
$line .= $list->[$i];
push ( @{$comb}, $line );
}
$n++;
}
}
If this indeed what your asking.
A
AB
ABC
ABCD
B
BC
BCD
C
CD
D
-----Original Message-----
From: Andrew Curry [mailto:andrew.curry@pa-sport.com]
Sent: 28 November 2007 15:43
To: Dan Klose; beginners@perl.org
Subject: RE: fixed list combinatorics
Not sure this exactly what you want but
use strict;
my ( @list, @comb );
@list = ( 1, 2, 3, 4 );
combinations( \@list, \@comb );
print join ( "\n", @comb );
sub combinations {
my ( $list, $comb ) = @_;
my ( $key, $i, $x, $line, @comb );
foreach my $key ( @{$list} ) {
$line = $key;
push ( @{$comb}, $line );
for ( my $i = $key ; $i <= $#list ; $i++ ) {
$line .= $list->[$i];
push ( @{$comb}, $line );
}
}
}
Runs and returns....
1
12
123
1234
2
23
234
3
34
4
-----Original Message-----
From: Dan Klose [mailto:perlmunky@googlemail.com]
Sent: 28 November 2007 14:32
To: beginners@perl.org
Subject: fixed list combinatorics
Hi list,
I am having a bad day and would really like some help (the coffee hasn't).
I have a list that looks like:
my @list = (1,2,3,4);
I would like to generate all patterns that follow:
1
2
3
4
12
123
23
34
234
1234
The list can be of any length and the next number in the list must be the
current number +1 ( i am not working with numbers - i think it is easier to
explain this way).
How do I do this? I did look at the Combinatorics module however it does
not impose fixed ordering as far as I can see.
Thanks
This e-mail is from the PA Group. For more information, see
www.thepagroup.com.
This e-mail may contain confidential information. Only the addressee is
permitted to read, copy, distribute or otherwise use this email or any
attachments. If you have received it in error, please contact the sender
immediately. Any opinion expressed in this e-mail is personal to the sender
and may not reflect the opinion of the PA Group.
Any e-mail reply to this address may be subject to interception or
monitoring for operational reasons or for lawful business practices.
--
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/
This e-mail is from the PA Group. For more information, see
www.thepagroup.com.
This e-mail may contain confidential information. Only the addressee is
permitted to read, copy, distribute or otherwise use this email or any
attachments. If you have received it in error, please contact the sender
immediately. Any opinion expressed in this e-mail is personal to the sender
and may not reflect the opinion of the PA Group.
Any e-mail reply to this address may be subject to interception or
monitoring for operational reasons or for lawful business practices.
| |
| Dan Klose 2007-11-28, 7:01 pm |
| Thanks for your help.
On Nov 28, 2007 3:51 PM, Andrew Curry <andrew.curry@pa-sport.com> wrote:
> Or a better one for none numeric's would be : I think.....
>
> use strict;
> my ( @list, @comb );
>
> @list = ( 'A', 'B', 'C', 'D' );
>
> combinations( \@list, \@comb );
>
> print join ( "\n", @comb );
>
> sub combinations {
> my ( $list, $comb ) = @_;
> my ( $key, $i, $x, $line, @comb, $n );
> $n = 1;
> foreach my $key ( @{$list} ) {
> $line = $key;
> push ( @{$comb}, $line );
>
> for ( my $i = $n ; $i <= $#list ; $i++ ) {
> $line .= $list->[$i];
> push ( @{$comb}, $line );
> }
> $n++;
> }
> }
>
> If this indeed what your asking.
>
> A
> AB
> ABC
> ABCD
> B
> BC
> BCD
> C
> CD
> D
>
> -----Original Message-----
> From: Andrew Curry [mailto:andrew.curry@pa-sport.com]
> Sent: 28 November 2007 15:43
> To: Dan Klose; beginners@perl.org
> Subject: RE: fixed list combinatorics
>
> Not sure this exactly what you want but
>
> use strict;
> my ( @list, @comb );
>
> @list = ( 1, 2, 3, 4 );
>
> combinations( \@list, \@comb );
>
> print join ( "\n", @comb );
>
> sub combinations {
> my ( $list, $comb ) = @_;
> my ( $key, $i, $x, $line, @comb );
>
> foreach my $key ( @{$list} ) {
> $line = $key;
> push ( @{$comb}, $line );
>
> for ( my $i = $key ; $i <= $#list ; $i++ ) {
> $line .= $list->[$i];
> push ( @{$comb}, $line );
> }
> }
> }
>
> Runs and returns....
>
> 1
> 12
> 123
> 1234
> 2
> 23
> 234
> 3
> 34
> 4
>
> -----Original Message-----
> From: Dan Klose [mailto:perlmunky@googlemail.com]
> Sent: 28 November 2007 14:32
> To: beginners@perl.org
> Subject: fixed list combinatorics
>
> Hi list,
>
> I am having a bad day and would really like some help (the coffee hasn't).
>
> I have a list that looks like:
> my @list = (1,2,3,4);
>
> I would like to generate all patterns that follow:
> 1
> 2
> 3
> 4
> 12
> 123
> 23
> 34
> 234
> 1234
>
>
> The list can be of any length and the next number in the list must be the
> current number +1 ( i am not working with numbers - i think it is easier
> to
> explain this way).
>
> How do I do this? I did look at the Combinatorics module however it does
> not impose fixed ordering as far as I can see.
>
> Thanks
>
>
> This e-mail is from the PA Group. For more information, see
> www.thepagroup.com.
>
> This e-mail may contain confidential information. Only the addressee is
> permitted to read, copy, distribute or otherwise use this email or any
> attachments. If you have received it in error, please contact the sender
> immediately. Any opinion expressed in this e-mail is personal to the
> sender
> and may not reflect the opinion of the PA Group.
>
> Any e-mail reply to this address may be subject to interception or
> monitoring for operational reasons or for lawful business practices.
>
>
>
>
>
> --
> To unsubscribe, e-mail: beginners-unsubscribe@perl.org
> For additional commands, e-mail: beginners-help@perl.org
> http://learn.perl.org/
>
>
>
> This e-mail is from the PA Group. For more information, see
> www.thepagroup.com.
>
> This e-mail may contain confidential information. Only the addressee is
> permitted to read, copy, distribute or otherwise use this email or any
> attachments. If you have received it in error, please contact the sender
> immediately. Any opinion expressed in this e-mail is personal to the
> sender
> and may not reflect the opinion of the PA Group.
>
> Any e-mail reply to this address may be subject to interception or
> monitoring for operational reasons or for lawful business practices.
>
>
>
>
>
| |
| Rob Dixon 2007-11-28, 7:01 pm |
| Dan Klose wrote:
> Hi list,
>
> I am having a bad day and would really like some help (the coffee hasn't).
>
> I have a list that looks like:
> my @list = (1,2,3,4);
>
> I would like to generate all patterns that follow:
> 1
> 2
> 3
> 4
> 12
> 123
> 23
> 34
> 234
> 1234
>
>
> The list can be of any length and the next number in the list must be the
> current number +1 ( i am not working with numbers - i think it is easier to
> explain this way).
>
> How do I do this? I did look at the Combinatorics module however it does
> not impose fixed ordering as far as I can see.
Hi Dan
I feel there must be a neater way, but the sledgehammer technique gives
me the code below.
HTH,
Rob
use strict;
use warnings;
my @list = 1..4;
foreach my $start (0 .. $#list) {
foreach my $end ($start .. $#list) {
my @sublist = @list[$start..$end];
print join('', @sublist), "\n";
}
}
**OUTPUT**
1
12
123
1234
2
23
234
3
34
4
| |
| Dr.Ruud 2007-11-28, 7:01 pm |
| "Dan Klose" schreef:
> Hi list,
>
> I am having a bad day and would really like some help (the coffee
> hasn't).
>
> I have a list that looks like:
> my @list = (1,2,3,4);
>
> I would like to generate all patterns that follow:
> 1
> 2
> 3
> 4
> 12
> 123
> 23
> 34
> 234
> 1234
>
>
> The list can be of any length and the next number in the list must be
> the current number +1 ( i am not working with numbers - i think it is
> easier to explain this way).
>
> How do I do this? I did look at the Combinatorics module however it
> does not impose fixed ordering as far as I can see.
Compare it to this list:
0000 .... X
0001 ...1
0010 ..2.
0011 ..21
0100 .3..
0101 .3.1 X
0110 .32.
0111 .321
1000 4...
1001 4..1 X
1010 4.2. X
1011 4.21 X
1100 43..
1101 43.1 X
1110 432.
1111 4321
It seems you want to filter out the all-empty and disconnected variants
(marked with X).
perl -wle'
print for grep /\S/ && !/\S\s+\S/,
map {
$_ = reverse sprintf("%b", $_);
tr/0/ /;
s/1/$-[0]+1/eg;
$_;
} 0..2**4-1
;
'
1
2
12
3
23
123
4
34
234
1234
Alternative:
$ perl -wle'
print for grep /\S/ && !/\S\s+\S/,
map {
($_ = reverse sprintf("%b", $_)) =~ tr/01/ 7/;
$_ &= "1234";
} 0..15
;
'
1
2
12
3
23
123
4
34
234
1234
--
Affijn, Ruud
"Gewoon is een tijger."
| |
|
|
| Dan Klose 2007-11-28, 7:01 pm |
| yeah sorry, I should have posted.
Thanks all for the solutions. Next time I will post if I get a
solution to the problem.
On 28 Nov 2007, at 19:58, yitzle wrote:
> In a personal email conversation, he realized what he was actually
> looking for is the power set.
> List::PowerSet
> http://search.cpan.org/~nikc/List-P...ist/PowerSet.pm
>
> --
> To unsubscribe, e-mail: beginners-unsubscribe@perl.org
> For additional commands, e-mail: beginners-help@perl.org
> http://learn.perl.org/
>
>
| |
|
|
| Xavier Noria 2007-11-28, 7:01 pm |
| On Nov 28, 2007, at 9:54 PM, Xavier Noria wrote:
> On Nov 28, 2007, at 8:58 PM, yitzle wrote:
>
>
> If speed is an issue Algorith::Combinatorics provides subsets() in XS:
I had done some benchmarks which are included in the distribution but
not this one.
I've found that List::PowerSet outperforms Algorithm::Combinatorics'
subset(). Time to revise that subroutine.
-- fxn
| |
| Dr.Ruud 2007-11-28, 7:01 pm |
| yitzle schreef:
> In a personal email conversation, he realized what he was actually
> looking for is the power set.
> List::PowerSet
> http://search.cpan.org/~nikc/List-P...ist/PowerSet.pm
#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
sub powerset {
my $set = shift;
my $powerset = [];
my $n = @$set;
for my $i (0 .. 2 ** $n - 1) {
my $subset = [];
for my $j (0 .. $n - 1) {
push @$subset, $set->[$j] if ($i & 2 ** $j);
}
push @$powerset, $subset;
}
return $powerset;
}
sub powersubset {
my ($set, $n, $i) if 0;
if (@_) {
if (ref $_[0] eq "ARRAY") {
$set = $_[0];
$n = @$set;
if (@_ > 1) {
$i = $_[1];
}
else {
$i = undef;
return;
}
}
else {
$i = $_[0];
}
}
else {
$i = (defined $i) ? $i + 1 : 0;
return if $i >= 2 ** $n;
}
my $subset = [];
for my $j (0 .. $n - 1) {
push @$subset, $set->[$j] if ($i & 2 ** $j);
}
return $subset;
}
my $set = ['foo', 'bar', 'baz'];
my $powerset = powerset($set);
print Dumper $powerset;
print "-"x40, "\n";
my $powersubset = powersubset($set);
print Dumper $powersubset;
$powersubset = powersubset() for 0..2;
print Dumper $powersubset;
$powersubset = powersubset($_) for 0..2;
print Dumper $powersubset;
$powersubset = powersubset() for 0..2;
print Dumper $powersubset;
print "-"x40, "\n";
powersubset($set);
while (defined($powersubset = powersubset())) {
print Dumper $powersubset;
}
print "-"x40, "\n";
$powersubset = powersubset($set, 2);
print Dumper $powersubset;
__END__
--
Affijn, Ruud
"Gewoon is een tijger."
| |
| Xavier Noria 2007-11-28, 10:00 pm |
| On Nov 28, 2007, at 10:37 PM, Xavier Noria wrote:
> On Nov 28, 2007, at 9:54 PM, Xavier Noria wrote:
>
>
> I had done some benchmarks which are included in the distribution
> but not this one.
>
> I've found that List::PowerSet outperforms Algorithm::Combinatorics'
> subset(). Time to revise that subroutine.
Indeed, the iterator provided by Algorithm::Combinatorics is faster
only for lists of sizes >= 7. (And gets to be twice as fast for size
16.)
The subroutine that gives you all the subsets in one shot has its own
implementation in List::PowerSet (it is not a wrapper around the
iterator). It is recursive and fast, and clever! I think it is that
fast because it actually runs basically in C:
[ map { [$first, @$_ ], [ @$_] } @$pow ];
given that map is an opcode.
For that call Algorithm::Combinatorics matches and performs slighly
better than List::PowerSet from size 14 on. I guess that's because it
creates less intermediate stuff.
Certainly there's room for improvement here.
-- fxn
| |
| John W . Krahn 2007-11-28, 10:00 pm |
| On Wednesday 28 November 2007 06:32, Dan Klose wrote:
> Hi list,
Hello,
> I am having a bad day and would really like some help (the coffee
> hasn't).
>
> I have a list that looks like:
> my @list = (1,2,3,4);
>
> I would like to generate all patterns that follow:
> 1
> 2
> 3
> 4
> 12
> 123
> 23
> 34
> 234
> 1234
>
>
> The list can be of any length and the next number in the list must be
> the current number +1 ( i am not working with numbers - i think it is
> easier to explain this way).
>
> How do I do this? I did look at the Combinatorics module however it
> does not impose fixed ordering as far as I can see.
Another way to do it:
$ perl -le'
my $list = join "", 1 .. 4;
for my $len ( 1 .. length $list ) {
for my $elem ( 0 .. length( $list ) - 1 ) {
my $out = substr $list, $elem, $len;
print $out if $len == length $out;
}
}
'
1
2
3
4
12
23
34
123
234
1234
John
--
use Perl;
program
fulfillment
| |
| Xavier Noria 2007-11-30, 4:00 am |
| On Nov 29, 2007, at 2:06 AM, Xavier Noria wrote:
> Indeed, the iterator provided by Algorithm::Combinatorics is faster
> only for lists of sizes >= 7. (And gets to be twice as fast for size
> 16.)
> Certainly there's room for improvement here.
For the archives, I copied the iterator in List::PowerSet and rewrote
it in XS for Algorithm::Combinatorics, that's up in the 0.25.
-- fxn
|
|
|
|
|