[Truffle] Add Array permutation/combination no block size implementat…

…ions
jruby · Jun 29, 2016 · 3910fc0 · 3910fc0
1 parent 81fdf12
commit 3910fc0
Showing 5 changed files with 51 additions and 15 deletions.
diff --git a/spec/truffle/tags/core/array/combination_tags.txt b/spec/truffle/tags/core/array/combination_tags.txt
diff --git a/spec/truffle/tags/core/array/permutation_tags.txt b/spec/truffle/tags/core/array/permutation_tags.txt
diff --git a/spec/truffle/tags/core/array/repeated_combination_tags.txt b/spec/truffle/tags/core/array/repeated_combination_tags.txt
diff --git a/spec/truffle/tags/core/array/repeated_permutation_tags.txt b/spec/truffle/tags/core/array/repeated_permutation_tags.txt
diff --git a/truffle/src/main/ruby/core/array.rb b/truffle/src/main/ruby/core/array.rb
@@ -195,7 +195,7 @@ def combination(num)
 
     unless block_given?
       return to_enum(:combination, num) do
-        self.combination_size(num)
+        combination_size(num)
       end
     end
 
@@ -600,7 +600,7 @@ def last(n=undefined)
   def permutation(num=undefined, &block)
     unless block_given?
       return to_enum(:permutation, num) do
-        Rubinius::Mirror::Array.reflect(self).permutation_size(num)
+        permutation_size(num)
       end
     end
 
@@ -637,6 +637,28 @@ def permutation(num=undefined, &block)
     self
   end
 
+  def permutation_size(num)
+    n = self.size
+    if undefined.equal? num
+      k = self.size
+    else
+      k = Rubinius::Type.coerce_to_collection_index num
+    end
+    descending_factorial(n, k)
+  end
+  private :permutation_size
+
+  def descending_factorial(from, how_many)
+    cnt = how_many >= 0 ? 1 : 0
+    while (how_many) > 0
+      cnt = cnt*(from)
+      from -= 1
+      how_many -= 1
+    end
+    cnt
+  end
+  private :descending_factorial
+
   def __permute__(num, perm, index, used, &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
@@ -717,7 +739,7 @@ def repeated_combination(combination_size, &block)
     combination_size = combination_size.to_i
     unless block_given?
       return to_enum(:repeated_combination, combination_size) do
-        Rubinius::Mirror::Array.reflect(self).repeated_combination_size(combination_size)
+        repeated_combination_size(combination_size)
       end
     end
 
@@ -749,7 +771,7 @@ def repeated_permutation(combination_size, &block)
     combination_size = combination_size.to_i
     unless block_given?
       return to_enum(:repeated_permutation, combination_size) do
-        Rubinius::Mirror::Array.reflect(self).repeated_permutation_size(combination_size)
+        repeated_permutation_size(combination_size)
       end
     end
 
@@ -766,6 +788,31 @@ def repeated_permutation(combination_size, &block)
     return self
   end
 
+  def repeated_permutation_size(combination_size)
+    return 0 if combination_size < 0
+    self.size ** combination_size
+  end
+  private :repeated_permutation_size
+
+  def repeated_combination_size(combination_size)
+    return 1 if combination_size == 0
+    return binomial_coefficient(combination_size, self.size + combination_size - 1)
+  end
+  private :repeated_combination_size
+
+  def binomial_coefficient(comb, size)
+    comb = size-comb if (comb > size-comb)
+    return 0 if comb < 0
+    descending_factorial(size, comb) / descending_factorial(comb, comb)
+  end
+  private :binomial_coefficient
+
+  def combination_size(num)
+    binomial_coefficient(num, self.size)
+  end
+  private :combination_size
+
+
   def compile_repeated_permutations(combination_size, place, index, &block)
     length.times do |i|
       place[index] = i