Skip to content

Instantly share code, notes, and snippets.

# 0racle/Permutations Last active Mar 13, 2018

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); # 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
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.