public
Last active

  • Download Gist
gistfile1.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.