PWC 054 › kth Permutation

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions 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.

Leave a Reply

Your email address will not be published. Required fields are marked *