From 6e82d3c1989660a7ade48d4bdf4be3af945a5994 Mon Sep 17 00:00:00 2001
From: jluehrs2 <jluehrs2@uiuc.edu>
Date: Sat, 2 Feb 2008 01:22:34 -0500
Subject: 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)

---
 lib/Games/Word.pm | 35 ++++++++++++++++++++++-------------
 1 file 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;
-- 
cgit v1.2.3-54-g00ecf