Three clicks could have taken you to Permuting with duplicates and no memory. Now it will only require one. (:
The link of mine that you originally linked to does what I usually think of as "counting" in a strange base (no, it isn't "combinations" in my book -- I'm curious what, if any, the official mathematical term for it is) and so would iterate through N**N cases, giving you many more than the N! cases you wanted.
Since you don't need to avoid duplicates, you can probably do it more simply. The documentation for Algorithm::Permute has links to some good examples.
...Looking at Permuting with duplicates and no memory to see if there were any obvious improvements to be had if you assume no duplicates, I realized that I can change sort to reverse which should make it rather faster (while still handling duplicates). I'd compare it to Algorithm::Permute but that is all written in XS which makes it: 1) unfair, and 2) too hard to get running at the moment. Maybe later. (:
Update: I compared the updated version of my code against the code that Algorithm::Permute includes in its sample benchmark code. My code beat all but the XS versions in speed (about 1/2 as fast as the XS version) and beat all of them in that my code handles duplicate items in the list while none of the others did. :)
-
tye
(but my friends call me "Tye")
| [reply] |
You can also go the inefficient but straightforward way,
just everywhere use an iterator, and compose iterators to get new iterators. And, of course, iterators can be built
out of closures. Try the following:
sub ret_permute_iter {
if (@_ < 2) {
my @vals = ("garbage", @_);
return sub {
shift @vals;
return @vals;
};
}
else {
my ($cur, @left) = @_;
my @done;
my $iter = ret_permute_iter(@left);
return sub {
my @res = $iter->();
if (@res) {
return ($cur, @res);
}
elsif (@left) {
push @done, $cur;
$cur = shift @left;
$iter = ret_permute_iter(@done, @left);
@res = $iter->();
return ($cur, @res);
}
else {
return;
}
};
}
}
my $demo_iterator = ret_permute_iter(1..5);
foreach (1..120) {
print $demo_iterator->(), "\n";
}
I won't compare speed to tye's because, um, I am much
slower. :-) But you can arrive at this iterator approach
from the standard list-based approach in a fairly
mechanical fashion, and it is worthwhile figuring out how I did that. | [reply]
[d/l] |
If you want to iterate on all the permutations of n elements, you could use Algorithm::Permute (which, IIRC, should contain even the code from Algorithm::FastPermute), with something like this (taken from docs):
my @array = (1..9);
Algorithm::Permute::permute { print "@array\n" } @array;
The block of code is executed for every permutation. | [reply]
[d/l] |