This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)
Task #1 this week is as follows:
Write a script to accept two integers n (>=1) and k (>=1). It should print the kth permutation of n integers. For more information, please follow the wiki page.
For example, for n=3 and k=4, the possible permutation sequences are 123, 132, 213, 231, 312, 321. The script should print the 4th permutation sequence, 231.
This is fairly straightforward. There are a number of easy ways to generate permutations that we’ve all seen time and time again, but as I need to optimize for programmer time this week, I’m going to use Algorithm::Combinatorics for my Perl solution. However, since it’s an efficient module, it’ll also optimize for processor time!
Perl
use Algorithm::Combinatorics qw<permutations>;
say join '', @{ ( permutations([1..$n], $n) )[$k-1] };
You can make this a bit more efficient (on average) by using the iterator version of permutations and stopping on the $kth iteration:
my $it = permutations([1..$n], $n);
$it->next for 1..$k-1;
say join '', @{ $it->next };
In benchmarks, the iterator performed 10-30% better on average, and was sometimes a bit worse, mainly due to function call and loop overhead.
You’d think this is a bit too easy, but that would be before you see the Raku solution.
Raku
say (1..$n).permutations[$k-1];
This one ended up being very easy, maybe a little too easy in Perl, but I didn’t see much point to re-inventing such a basic wheel.