sondeen@isi.edu (Jeff Sondeen) (01/17/91)
Could someone explain why the following permutating perl program doesn't
work? The idea is to generate all permutations of a list 1..$siz (for
example, input of 3 should yield (1,2,3) (1,3,2) (2,3,1) (2,1,3) (3,1,2) and
(3,2,1), but it doesn't. It just does (1,2,3), as follows
perl permute.p 3
len:3 i:1 ins: 1 2 3 outs:
len:2 i:1 ins: 2 3 outs: 1
len:1 i:1 ins: 3 outs: 1 2
1 2 3
len:1 i:1 ins: 3 outs: 1 2
len:2 i:2 ins: 3 2 outs: 1
len:3 i:1 ins: 2 3 1 outs:
It might be that somehow the local variable $i is getting clobbered
(acting like a global???)
perl program follows: ------------------------------------------------------
$siz = @ARGV[0];
@terms = (1..$siz);
do permute($siz,@terms,());
exit;
sub permute {
local($len,@outs) = @_;
local(@ins) = splice(@outs,0,$len);
local($i,$out);
if ($len > 0) {
for $i (1..$len) {
print "len:$len i:$i ins: @ins outs: @outs\n";
$out = shift(@ins);
do permute($len-1,@ins,@outs,$out);
push(@ins,$out);
print "len:$len i:$i ins: @ins outs: @outs\n";
}
} else {
print "@outs\n";
}
}
--
/jeff sondeen@isi.edu "engineers were discouraged
from bringing problems to the attention of their supervisors"
-- John Magnus, final report, Hubble Space Telescope investigationtchrist@convex.COM (Tom Christiansen) (01/17/91)
From the keyboard of sondeen@venera.isi.edu (Jeff Sondeen):
:Could someone explain why the following permutating perl program doesn't
:work? The idea is to generate all permutations of a list 1..$siz (for
:example, input of 3 should yield (1,2,3) (1,3,2) (2,3,1) (2,1,3) (3,1,2) and
:(3,2,1), but it doesn't. It just does (1,2,3), as follows
:perl permute.p 3
:len:3 i:1 ins: 1 2 3 outs:
:len:2 i:1 ins: 2 3 outs: 1
:len:1 i:1 ins: 3 outs: 1 2
:1 2 3
:len:1 i:1 ins: 3 outs: 1 2
:len:2 i:2 ins: 3 2 outs: 1
:len:3 i:1 ins: 2 3 1 outs:
On my system it does the whole thing, so I wonder whether you
are running an older version of perl that has the iterator-
during-recursion bug. I'm running PL44, and it works fine.
A couple things I noticed that won't make any difference, but
did still look odd anyway.
:$siz = @ARGV[0];
You actually mean $ARGV[0], since you want a scalar, not an
array here.
:@terms = (1..$siz);
:do permute($siz,@terms,());
Not sure what the null list there is for. Perl isn't like
C which needs a null at the end of a list for variatic functions.
In fact, as far as I can tell, empty lists are squished away
entirely. This is demo'd by this code chunk, which things
they're all just 4 anyway.
do count(1..4);
do count(1..4, ());
do count((), 1..4, ());
do count(@x, 1..4, ());
sub count {
print "found ",1+$#_, " items\n";
}
--tom
--
"Hey, did you hear Stallman has replaced /vmunix with /vmunix.el? Now
he can finally have the whole O/S built-in to his editor like he
always wanted!" --me (Tom Christiansen <tchrist@convex.com>)