ruby-changes:2099
From: ko1@a...
Date: 2 Oct 2007 08:35:45 +0900
Subject: [ruby-changes:2099] matz - Ruby:r13590 (trunk): * array.c (rb_ary_permutation): implementation contributed from
matz 2007-10-02 08:35:30 +0900 (Tue, 02 Oct 2007)
New Revision: 13590
Modified files:
trunk/ChangeLog
trunk/array.c
trunk/test/ruby/test_array.rb
Log:
* array.c (rb_ary_permutation): implementation contributed from
David Flanagan. [ruby-core:12344]
* array.c (rb_ary_combination): RDoc update to clarify. a patch
from David Flanagan. [ruby-core:12344]
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/array.c?r1=13590&r2=13589
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/ChangeLog?r1=13590&r2=13589
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/test/ruby/test_array.rb?r1=13590&r2=13589
Index: array.c
===================================================================
--- array.c (revision 13589)
+++ array.c (revision 13590)
@@ -2954,37 +2954,95 @@
return Qnil;
}
-static long
-perm_len(long n, long k)
-{
- long i, val = 1;
+/*
+ * 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
+ * values: the Ruby array that holds the actual values to permute
+ */
+static void
+permute0(long n, long r, long p[], long index, int used[], VALUE values) {
+ long i,j;
+ for(i = 0; i < n; i++) {
+ if (used[i] == 0) {
+ p[index] = i;
+ if (index < r-1) { /* if not done yet */
+ used[i] = 1; /* mark index used */
+ permute0(n,r,p,index+1, /* recurse */
+ used, values);
+ used[i] = 0; /* index unused */
+ }
+ else {
+ /* We have a complete permutation of array indexes */
+ /* Build a ruby array of the corresponding values */
+ /* And yield it to the associated block */
+ VALUE result = rb_ary_new2(r);
+ VALUE *result_array = RARRAY_PTR(result);
+ VALUE *values_array = RARRAY_PTR(values);
- while (n > k) {
- val *= n--;
+ for(j = 0; j < r; j++) result_array[j] = values_array[p[j]];
+ RARRAY(result)->len = r;
+ rb_yield(result);
+ }
+ }
}
- return val;
}
/*
* call-seq:
- * ary.permutation(n)
+ * ary.permutation(n) { |p| block } -> array
+ * ary.permutation(n) -> enumerator
*
- * Returns an array of all permutations of length <i>n</i> of
- * elements from <i>ary</i>].
- *
+ * 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.
+ * 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(0).to_a #=> []
* 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(4).to_a #=> []
- *
+ * a.permutation(0).to_a #=> [[]]: one permutation of length 0
+ * a.permutation(4).to_a #=> [] : no permutations of length 4
*/
static VALUE
rb_ary_permutation(VALUE ary, VALUE num)
{
- /* TBD */
+ RETURN_ENUMERATOR(ary, 1, &num); /* Return enumerator if no block */
+ long r = NUM2LONG(num); /* Permutation size from argument */
+ long n = RARRAY_LEN(ary); /* Array length */
+ long i;
+
+ if (r < 0 || n < r) {
+ /* no permutations: yield nothing */
+ }
+ else if (r == 0) { /* exactly one permutation: the zero-length array */
+ rb_yield(rb_ary_new2(0));
+ }
+ else if (r == 1) { /* this is a special, easy case */
+ for (i = 0; i < RARRAY_LEN(ary); i++) {
+ rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
+ }
+ }
+ else { /* this is the general case */
+ ary = rb_ary_dup(ary); /* private defensive copy of ary */
+ long p[n];
+ int used[n];
+ for(i = 0; i < n; i++) used[i] = 0; /* initialize array */
+
+ permute0(n,r,p,0,used,ary); /* compute and yield permutations */
+ }
+ return ary;
}
static long
@@ -3005,18 +3063,24 @@
/*
* call-seq:
- * ary.combination(n)
+ * ary.combination(n) { |c| block } -> ary
+ * ary.combination(n) -> enumerator
*
- * Returns an enumerator of all combinations of length <i>n</i> of
- * elements from <i>ary</i>].
+ * When invoked with a block, yields all combinations of length <i>n</i>
+ * of elements from <i>ary</i> and then returns <i>ary</i> itself.
+ * The implementation makes no guarantees about the order in which
+ * the combinations are yielded.
+ *
+ * When invoked without a block, returns an enumerator object instead.
*
+ * Examples:
* a = [1, 2, 3, 4]
- * a.combination(0).to_a #=> []
* a.combination(1).to_a #=> [[1],[2],[3],[4]]
* a.combination(2).to_a #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
* a.combination(3).to_a #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
* a.combination(4).to_a #=> [[1,2,3,4]]
- * a.combination(5).to_a #=> []
+ * a.combination(0).to_a #=> [[]]: one combination of length 0
+ * a.combination(5).to_a #=> [] : no combinations of length 5
*
*/
@@ -3028,10 +3092,10 @@
RETURN_ENUMERATOR(ary, 1, &num);
n = NUM2LONG(num);
len = RARRAY_LEN(ary);
- if (len < n) {
+ if (n < 0 || len < n) {
/* yield nothing */
}
- else if (n <= 0) {
+ else if (n == 0) {
rb_yield(rb_ary_new2(0));
}
else if (n == 1) {
@@ -3187,7 +3251,7 @@
rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, 0);
rb_define_method(rb_cArray, "choice", rb_ary_choice, 0);
rb_define_method(rb_cArray, "cycle", rb_ary_cycle, 0);
- /* rb_define_method(rb_cArray, "permutation", rb_ary_permutation, 1); */
+ rb_define_method(rb_cArray, "permutation", rb_ary_permutation, 1);
rb_define_method(rb_cArray, "combination", rb_ary_combination, 1);
rb_define_method(rb_cArray, "product", rb_ary_product, 1);
Index: ChangeLog
===================================================================
--- ChangeLog (revision 13589)
+++ ChangeLog (revision 13590)
@@ -1,3 +1,11 @@
+Tue Oct 2 08:25:50 2007 Yukihiro Matsumoto <matz@r...>
+
+ * array.c (rb_ary_permutation): implementation contributed from
+ David Flanagan. [ruby-core:12344]
+
+ * array.c (rb_ary_combination): RDoc update to clarify. a patch
+ from David Flanagan. [ruby-core:12344]
+
Tue Oct 2 07:01:05 2007 Koichi Sasada <ko1@a...>
* proc.c (proc_dup): proc->block.proc should be self.
@@ -5,11 +13,6 @@
* bootstraptest/test_knownbug.rb, test_method.rb:
move a fixed test.
-Mon Oct 1 23:44:23 2007 Yukihiro Matsumoto <matz@r...>
-
- * array.c (rb_ary_combination): revisit #combination behavior.
- suggested by David Flanagan.
-
Mon Oct 1 16:17:44 2007 Tanaka Akira <akr@f...>
* bootstraptest/test_method.rb: use assert_normal_exit to test
Index: test/ruby/test_array.rb
===================================================================
--- test/ruby/test_array.rb (revision 13589)
+++ test/ruby/test_array.rb (revision 13590)
@@ -1177,14 +1177,6 @@
assert_equal(@cls[1,2], @cls[1, 2] | @cls[1, 2])
end
-# def test_permutation
-# assert_equal(@cls[[]], @cls[1,2,3].permutation(0).to_a)
-# assert_equal(@cls[[1],[2],[3]], @cls[1,2,3].permutation(1).to_a)
-# assert_equal(@cls[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]], @cls[1,2,3].permutation(2).to_a)
-# assert_equal(@cls[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]], @cls[1,2,3].permutation(3).to_a)
-# assert_equal(@cls[], @cls[1,2,3].permutation(4).to_a)
-# end
-
def test_combination
assert_equal(@cls[[]], @cls[1,2,3,4].combination(0).to_a)
assert_equal(@cls[[1],[2],[3],[4]], @cls[1,2,3,4].combination(1).to_a)
@@ -1199,4 +1191,20 @@
@cls[1,2,3].product([4,5]))
assert_equal(@cls[[1,1],[1,2],[2,1],[2,2]], @cls[1,2].product([1,2]))
end
+
+ def test_permutation
+ a = @cls[1,2,3]
+ assert_equal(@cls[[]], a.permutation(0).to_a)
+ assert_equal(@cls[[1],[2],[3]], a.permutation(1).to_a.sort)
+ assert_equal(@cls[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]],
+ a.permutation(2).to_a.sort)
+ assert_equal(@cls[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]],
+ a.permutation(3).sort.to_a)
+ assert_equal(@cls[], a.permutation(4).to_a)
+ assert_equal(@cls[], a.permutation(-1).to_a)
+ assert_equal("abcde".each_char.to_a.permutation(5).sort,
+ "edcba".each_char.to_a.permutation(5).sort)
+ assert_equal(@cls[].permutation(0).to_a, @cls[[]])
+
+ end
end
--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml