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