Skip to content

Commit

Permalink
Showing 5 changed files with 51 additions and 15 deletions.
2 changes: 0 additions & 2 deletions spec/truffle/tags/core/array/combination_tags.txt

This file was deleted.

4 changes: 0 additions & 4 deletions spec/truffle/tags/core/array/permutation_tags.txt

This file was deleted.

3 changes: 0 additions & 3 deletions spec/truffle/tags/core/array/repeated_combination_tags.txt

This file was deleted.

2 changes: 0 additions & 2 deletions spec/truffle/tags/core/array/repeated_permutation_tags.txt

This file was deleted.

55 changes: 51 additions & 4 deletions truffle/src/main/ruby/core/array.rb
Original file line number Diff line number Diff line change
@@ -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

0 comments on commit 3910fc0

Please sign in to comment.