Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.