Sorry for the delay. I have been thinking about this problem off and on for
the last 2 weeks. This is my second try. Could this be done any more
efficiently? Thanks.
#!/usr/bin/perl
use warnings;
use strict;
my @data = 1 .. 4; # qw(man bites dog);
permute([EMAIL PROTECTED]);
sub permute {
my $ref = ref $_[0] eq 'ARRAY' ? shift : [EMAIL PROTECTED];
foreach my $i( 0 .. $#$ref ) {
# Is this efficient?
my @circular = @$ref[0 .. $i-1, $i+1 .. $#$ref];
foreach ( 0 .. $#circular ) {
foreach ( 1 .. $#circular ) {
print join(' ', $ref->[$i], @circular), "\n";
# Is this efficient?
push @circular, splice @circular, 1, 1;
}
# Is this efficient?
push @circular, shift @circular;
}
}
}
-----Original Message-----
From: David J Kirol
Sent: Sunday, June 27, 2004 9:30 PM
To: Zeus Odin
Subject: Re: How efficient is this permutation algorithm?
Your permute is not actually doing a permutation.
if @data is set to 1 .. 4, your algorithm yields:
1 2 3 4
1 3 4 2
1 4 2 3
2 1 3 4
2 3 4 1
2 4 1 3
3 1 2 4
3 2 4 1
3 4 1 2
4 1 2 3
4 2 3 1
4 3 1 2
fully half the permutations are missing. Condider:
1 2 3 4
m 1 2 4 3
1 3 4 2
m 1 3 2 4
1 4 2 3
m 1 4 3 2
2 1 3 4
m 2 1 4 3
2 3 4 1
m 2 3 1 4
2 4 1 3
m 2 4 3 1
3 1 2 4
m 3 1 4 2
3 2 4 1
m 3 2 1 4
3 4 1 2
m 3 4 2 1
4 1 2 3
m 4 1 3 2
4 2 3 1
m 4 2 1 3
4 3 1 2
m 4 3 2 1
Each 'missing' permutation is labeled with an 'm'.
HTH
Dave
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
<http://learn.perl.org/> <http://learn.perl.org/first-response>
