gistfile1.txt

From d40c40cd45ee504e8c056e3adc2e56557298c3b3 Mon Sep 17 00:00:00 2001
From: Matt Daw <matt@matt-daws-macbook-pro.local>
Date: Wed, 30 Dec 2009 13:01:26 -0500
Subject: [PATCH] Implement Array#permutation.

---
 kernel/common/array.rb                         |   83 ++++++++++++++++++++++++
 spec/tags/ruby/core/array/permutation_tags.txt |   10 ---
 2 files changed, 83 insertions(+), 10 deletions(-)
 delete mode 100644 spec/tags/ruby/core/array/permutation_tags.txt

diff --git a/kernel/common/array.rb b/kernel/common/array.rb
index c923ff9..bc8d405 100644
--- a/kernel/common/array.rb
+++ b/kernel/common/array.rb
@@ -957,6 +957,59 @@ class Array
     Packer.new(self,schema).dispatch
   end
 
+  ##
+  #  call-seq:
+  #     ary.permutation { |p| block }          -> array
+  #     ary.permutation                        -> enumerator
+  #     ary.permutation(n) { |p| block }       -> array
+  #     ary.permutation(n)                     -> enumerator
+  #
+  #  When invoked with a block, yield all permutations of length <i>n</i>
+  #  of the elements of <i>ary</i>, then return the array itself.
+  #  If <i>n</i> is not specified, yield all permutations of all elements.
+  #  The implementation makes no guarantees about the order in which 
+  #  the permutations are yielded.
+  #
+  #  When invoked without a block, return an enumerator object instead.
+  #
+  #  Examples:
+  #
+  #     a = [1, 2, 3]
+  #     a.permutation.to_a     #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
+  #     a.permutation(1).to_a  #=> [[1],[2],[3]]
+  #     a.permutation(2).to_a  #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
+  #     a.permutation(3).to_a  #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
+  #     a.permutation(0).to_a  #=> [[]] # one permutation of length 0
+  #     a.permutation(4).to_a  #=> []   # no permutations of length 4
+  #
+  def permutation(num=undefined, &block)
+    if num.equal? undefined
+      num = @total
+    else
+      num = Type.coerce_to num, Fixnum, :to_int
+    end
+    
+    return to_enum(:permutation, num) unless block_given?
+    
+    if num < 0 || @total < num
+      # no permutations, yield nothing
+    elsif num == 0
+      # exactly one permutation: the zero-length array
+      yield []
+    elsif num == 1
+      # this is a special, easy case
+      each { |val| yield [val] }
+    else
+      # this is the general case
+      p = Array.new(@total)
+      used = Array.new(@total, false)
+      
+      permute(@total, num, p, 0, used, block)
+    end
+    
+    self
+  end
+  
   # Removes and returns the last element from the Array.
   def pop(many=undefined)
     if many.equal? undefined
@@ -1729,6 +1782,36 @@ class Array
     end
   end
   private :isort_block!
+  
+  # Recursively compute permutations of r elements of the set [0..n-1].
+  # When we have a complete permutation of array indexes, copy the values
+  # at those indexes into a new array and yield that array. 
+  #
+  # n: the size of the set 
+  # r: the number of elements in each permutation
+  # p: the array (of size r) that we're filling in
+  # index: what index we're filling in now
+  # used: an array of booleans: whether a given index is already used
+  def permute(n, r, p, index, used, block)
+    for i in (0..n-1)
+      unless used[i]
+        p[index] = i
+        
+        if index < r-1
+          used[i] = true
+          permute(n, r, p, index+1, used, block)
+          used[i] = false
+        else
+          result = Array.new(r)
+          for j in (0..r-1)
+            result[j] = self[p[j]]
+          end
+          block.call(result)
+        end
+      end
+    end
+  end
+  private :permute
 
   def __rescue_match__(exception)
     i = to_iter
diff --git a/spec/tags/ruby/core/array/permutation_tags.txt b/spec/tags/ruby/core/array/permutation_tags.txt
deleted file mode 100644
index 4a1b898..0000000
--- a/spec/tags/ruby/core/array/permutation_tags.txt
+++ /dev/null
@@ -1,10 +0,0 @@
-fails:Array#permutation returns an Enumerator of all permutations when called without a block or arguments
-fails:Array#permutation returns an Enumerator of permutations of given length when called with an argument but no block
-fails:Array#permutation yields all permutations to the block then returns self when called with block but no arguments
-fails:Array#permutation yields all permutations of given length to the block then returns self when called with block and argument
-fails:Array#permutation returns the empty permutation ([[]]) when the given length is 0
-fails:Array#permutation returns the empty permutation([]) when called on an empty Array
-fails:Array#permutation returns no permutations when the given length has no permutations
-fails:Array#permutation handles duplicate elements correctly
-fails:Array#permutation handles nested Arrays correctly
-fails:Array#permutation truncates Float arguments
-- 
1.6.4