iteration

[Guest_imported]

how would you create a fuction that outputs all the posible combinations of a series of characters
eg.
list of chars = 1, 2, 3
output=
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

[sackyhack]

The first idea that came to mind and is probably
really inefficient:

sub permute_and_print {
	my $pre = shift;
	my @p = @_;
	if ($#p >= 0) {
		foreach $i (0..$#p) {
			my @newp = @p;
			my $newpre = $pre . " " . splice(@newp, $i, 1);
			permute_and_print($newpre, @newp);
		}
	}
	else {
		print $pre, "\n";
	}
}

sub permute {
	my @p = @_;
	permute_and_print("", @p);
}

@a = qw(1 2 3);
permute(@a);

print "\n\n";

@a = qw(a b c d e);
permute(@a);

 

[sophisticate]

Well, for being off the top of the head, sackyhack's idea works pretty well. The following took some research. This is another variation that benchmarks a bit faster, especially when permuting a larger set.

sub permute(@) {
@items = @_;
@set = (0..(@items - 1));
print @items,"\n";
while(@set = permutation(@set)) {
print map @items[$_], @set;
print "\n";
}
return 1;
}

sub permutation(@) {
my @r = @_;
my @tail = pop @r;
while (@r and $r[-1] > $tail[-1]) {
push @tail, pop @r;
}
if (defined(my $extra = pop @r)) {
my($place) = grep $extra < $tail[$_], 0..$#tail;
($extra, $tail[$place]) = ($tail[$place], $extra);
@r = ( @r, $extra, @tail );
} else {
return ();
}
return @r;
}

permute( qw/ a b c d e f / );

And to give credit where credit is due: this was inspired by the List:ermutor module ... which is probably better than any of these embedded options anyway.

Have fun,

brendanc@icehouse.net