use a better algorithm for generating random permutations (one that isn't limited by the ability of the factorial of the input length to fit into 32 bits)

1 files changed, 22 insertions, 13 deletions

diff --git a/lib/Games/Word.pm b/lib/Games/Word.pm
index 7b281f5..ba3a03a 100644
--- a/lib/Games/Word.pm
+++ b/lib/Games/Word.pm
@@ -13,38 +13,47 @@ use Test::Deep::NoTest;
 
 sub random_permutation {
     my $word = shift;
+
+    return '' unless $word;
+
+    my $letter = substr $word, int(rand length $word), 1, '';
+
+    return $letter . random_permutation($word);
+}
+
+sub is_permutation {
+    my @word_letters = split //, shift;
+    my @perm_letters = split //, shift;
+
+    return eq_deeply(\@word_letters, bag(@perm_letters));
+}
+
+sub _permutation {
+    my $word = shift;
     my $perm_index = shift;
 
     return '' if $word eq '';
 
-    use integer;
-
     my $len = length $word;
-    $perm_index = defined($perm_index) ? $perm_index :
-                                         int rand factorial $len;
     die "invalid permutation index" if $perm_index >= factorial($len) ||
                                        $perm_index < 0;
+
+    use integer;
+
     my $current_index = $perm_index / factorial($len - 1);
     my $rest = $perm_index % factorial($len - 1);
 
     my $first_letter = substr($word, $current_index, 1);
     substr($word, $current_index, 1) = '';
 
-    return $first_letter . random_permutation($word, $rest);
-}
-
-sub is_permutation {
-    my @word_letters = split //, shift;
-    my @perm_letters = split //, shift;
-
-    return eq_deeply(\@word_letters, bag(@perm_letters));
+    return $first_letter . _permutation($word, $rest);
 }
 
 sub all_permutations {
     my $word = shift;
 
     my @ret = ();
-    push @ret, random_permutation($word, $_)
+    push @ret, _permutation($word, $_)
         for 0..(factorial(length $word) - 1);
 
     return @ret;