Create a gist now

Instantly share code, notes, and snippets.

@0racle /Permutations
Last active Mar 13, 2018

Embed
Permutation Iterator
#!/usr/bin/env perl6
#`[
This is a quick example implementation of a permutation
iterator that uses a factorial calculation to quickly
return `.elems` on a permutation, and can efficiently
skip elements of enormous sequences.
This is just an example to showcase the special Iterator
methods... Not be a fast permutation generator.
I found this `nth-perm` function online and converted it
to Perl 6. I havent verified the algorithm is accurate.
]
sub permute(@l) {
Seq.new: class :: does Iterator {
has $!n = 0;
has $!elems = fac(@l.elems);
sub fac($n) { [×] 1 .. $n }
sub nth-perm(@S is copy, \k) {
my @P = [];
my $k = k;
while @S.elems {
my $f = fac(@S.end);
my $i = ($k ÷ $f).floor;
my $x = @S[$i];
$k = $k % $f;
@P.push: $x;
@S = |@S[0 ..^ $i], |@S[$i + 1 .. *];
}
return @P
}
method count-only { $!elems - $!n }
method skip-one { $!n++; self }
method skip-at-least(\i) { $!n += i }
method bool-only { self.count-only.Bool }
method pull-one {
$!n < $!elems
?? nth-perm(@.l, $!n++)
!! IterationEnd
}
}.new()
}
my @l = 'A'..'Z';
say permute(@l).elems;
# OUTPUT: 403291461126605635584000000
say permute(@l).skip(268860974084403757046816342)[0];
# OUTPUT: [R I J Z Y X W V U T S Q P O N K E H B L M D F C A G]
say "Completed in { now - INIT now } seconds";
# OUTPUT: Completed in 0.0531508 seconds
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment