[ruby-dev:40597] Re: [ruby-list:46898] 重複組合せは組込みにならないのでしょうか？
From:
"KISHIMOTO, Makoto" <ksmakoto@...4u.or.jp>
Date:
2010-03-12 06:49:24 UTC
List:
ruby-dev #40597
きしもとです > ソートルーチンのテストデータを生成しようとして思ったのですが、 > 順列と組合せは組込みになりましたが、重複組合せは組込みにならないのでしょうか？ 組込みの重複順列と重複組合せを実装してみました。 よければ検討お願いします。 Feature #2673 ( http://redmine.ruby-lang.org/issues/show/2673 ) と 同じような機能追加が考えられます（が、やっていません）。 2つ目のパッチは、重複でない組合せに引数なしを追加するものです。 （重複でない組合せだけ、引数なしを受け付けない（あってもあまり意味ないんですが） というのも変かなという気がするので）
Attachments (2)
repeated_patch.txt
(11 KB, text/x-diff)
Index: array.c
===================================================================
--- array.c (revision 26872)
+++ array.c (working copy)
@@ -4047,7 +4047,200 @@
}
/*
+ * Recursively compute repeated permutations of r elements of the set
+ * [0..n-1].
+ * When we have a complete repeated 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
+ * values: the Ruby array that holds the actual values to permute
+ */
+static void
+rpermute0(long n, long r, long *p, long index, VALUE values)
+{
+ long i, j;
+ for (i = 0; i < n; i++) {
+ p[index] = i;
+ if (index < r-1) { /* if not done yet */
+ rpermute0(n, r, p, index+1, values); /* recurse */
+ }
+ 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);
+ const VALUE *values_array = RARRAY_PTR(values);
+
+ for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
+ ARY_SET_LEN(result, r);
+ rb_yield(result);
+ if (RBASIC(values)->klass) {
+ rb_raise(rb_eRuntimeError, "repeated permute reentered");
+ }
+ }
+ }
+}
+
+/*
* call-seq:
+ * ary.repeated_permutation { |p| block } -> array
+ * ary.repeated_permutation -> enumerator
+ * ary.repeated_permutation(n) { |p| block } -> array
+ * ary.repeated_permutation(n) -> enumerator
+ *
+ * When invoked with a block, yield all repeated 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 repeated permutations of all
+ * elements.
+ * The implementation makes no guarantees about the order in which
+ * the repeated permutations are yielded.
+ *
+ * When invoked without a block, return an enumerator object instead.
+ *
+ * Examples:
+ *
+ * a = [1, 2]
+ * a.repeated_permutation.to_a #=> [[1,1],[1,2],[2,1],[2,2]]
+ * a.repeated_permutation(1).to_a #=> [[1], [2]]
+ * a.repeated_permutation(2).to_a #=> [[1,1],[1,2],[2,1],[2,2]]
+ * a.repeated_permutation(3).to_a #=> [[1,1,1],[1,1,2],[1,2,1],[1,2,2],
+ * # [2,1,1],[2,1,2],[2,2,1],[2,2,2]]
+ * a.repeated_permutation(0).to_a #=> [[]] # one permutation of length 0
+ */
+
+static VALUE
+rb_ary_repeated_permutation(int argc, VALUE *argv, VALUE ary)
+{
+ VALUE num;
+ long r, n, i;
+
+ n = RARRAY_LEN(ary); /* Array length */
+ RETURN_ENUMERATOR(ary, argc, argv); /* Return enumerator if no block */
+ rb_scan_args(argc, argv, "01", &num);
+ r = NIL_P(num) ? n : NUM2LONG(num); /* Permutation size from argument */
+
+ if (r < 0) {
+ /* 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 */
+ volatile VALUE t0 = tmpbuf(n, sizeof(long));
+ long *p = (long*)RSTRING_PTR(t0);
+ VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
+ RBASIC(ary0)->klass = 0;
+
+ rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */
+ tmpbuf_discard(t0);
+ RBASIC(ary0)->klass = rb_cArray;
+ }
+ return ary;
+}
+
+static void
+rcombinate0(long n, long r, long *p, long index, long rest, VALUE values)
+{
+ long j;
+ if (rest > 0) {
+ for (; index < n; ++index) {
+ p[r-rest] = index;
+ rcombinate0(n, r, p, index, rest-1, values);
+ }
+ }
+ else {
+ VALUE result = rb_ary_new2(r);
+ VALUE *result_array = RARRAY_PTR(result);
+ const VALUE *values_array = RARRAY_PTR(values);
+
+ for (j = 0; j < r; ++j) result_array[j] = values_array[p[j]];
+ ARY_SET_LEN(result, r);
+ rb_yield(result);
+ if (RBASIC(values)->klass) {
+ rb_raise(rb_eRuntimeError, "repeated combination reentered");
+ }
+ }
+}
+
+/*
+ * call-seq:
+ * ary.repeated_combination { |c| block } -> ary
+ * ary.repeated_combination -> enumerator
+ * ary.repeated_combination(n) { |c| block } -> ary
+ * ary.repeated_combination(n) -> enumerator
+ *
+ * When invoked with a block, yields all repeated 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 repeated combinations are yielded.
+ *
+ * When invoked without a block, returns an enumerator object instead.
+ *
+ * Examples:
+ *
+ * a = [1, 2, 3]
+ * a.repeated_combination.to_a #=> [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
+ * # [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]
+ * a.repeated_combination(1).to_a #=> [[1], [2], [3]]
+ * a.repeated_combination(2).to_a #=> [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
+ * a.repeated_combination(3).to_a #=> [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
+ * # [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]
+ * a.repeated_combination(4).to_a #=> [[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,2,2],[1,1,2,3],
+ * # [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
+ * # [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]]
+ * a.repeated_combination(0).to_a #=> [[]] # one combination of length 0
+ *
+ */
+
+static VALUE
+rb_ary_repeated_combination(int argc, VALUE *argv, VALUE ary)
+{
+ VALUE num;
+ long n, i, len;
+
+ RETURN_ENUMERATOR(ary, argc, argv); /* Return enumerator if no block */
+ len = RARRAY_LEN(ary);
+ rb_scan_args(argc, argv, "01", &num);
+ n = NIL_P(num) ? len : NUM2LONG(num); /* Combination size from argument */
+ if (n < 0) {
+ /* yield nothing */
+ }
+ else if (n == 0) {
+ rb_yield(rb_ary_new2(0));
+ }
+ else if (n == 1) {
+ for (i = 0; i < len; i++) {
+ rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
+ }
+ }
+ else if (len == 0) {
+ /* yield nothing */
+ }
+ else {
+ volatile VALUE t0 = tmpbuf(n, sizeof(long));
+ long *p = (long*)RSTRING_PTR(t0);
+ VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
+ RBASIC(ary0)->klass = 0;
+
+ rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */
+ tmpbuf_discard(t0);
+ RBASIC(ary0)->klass = rb_cArray;
+ }
+ return ary;
+}
+
+/*
+ * call-seq:
* ary.product(other_ary, ...)
*
* Returns an array of all combinations of elements from all arrays.
@@ -4332,6 +4525,8 @@
rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -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, "repeated_permutation", rb_ary_repeated_permutation, -1);
+ rb_define_method(rb_cArray, "repeated_combination", rb_ary_repeated_combination, -1);
rb_define_method(rb_cArray, "product", rb_ary_product, -1);
rb_define_method(rb_cArray, "take", rb_ary_take, 1);
Index: test/ruby/test_array.rb
===================================================================
--- test/ruby/test_array.rb (revision 26872)
+++ test/ruby/test_array.rb (working copy)
@@ -797,6 +797,40 @@
assert_match(/reentered/, e.message)
end
+ def test_repeated_permutation_with_callcc
+ respond_to?(:callcc, true) or require 'continuation'
+ n = 1000
+ cont = nil
+ ary = [1,2,3]
+ begin
+ ary.repeated_permutation {
+ callcc {|k| cont = k} unless cont
+ }
+ rescue => e
+ end
+ n -= 1
+ cont.call if 0 < n
+ assert_instance_of(RuntimeError, e)
+ assert_match(/reentered/, e.message)
+ end
+
+ def test_repeated_combination_with_callcc
+ respond_to?(:callcc, true) or require 'continuation'
+ n = 1000
+ cont = nil
+ ary = [1,2,3]
+ begin
+ ary.repeated_combination {
+ callcc {|k| cont = k} unless cont
+ }
+ rescue => e
+ end
+ n -= 1
+ cont.call if 0 < n
+ assert_instance_of(RuntimeError, e)
+ assert_match(/reentered/, e.message)
+ end
+
def test_hash
a1 = @cls[ 'cat', 'dog' ]
a2 = @cls[ 'cat', 'dog' ]
@@ -1403,6 +1437,54 @@
assert_equal(@cls[1, 2, 3, 4].permutation.to_a, b)
end
+ def test_repeated_permutation
+ a = @cls[1,2]
+ assert_equal(@cls[[]], a.repeated_permutation(0).to_a)
+ assert_equal(@cls[[1],[2]], a.repeated_permutation(1).to_a.sort)
+ assert_equal(@cls[[1,1],[1,2],[2,1],[2,2]],
+ a.repeated_permutation(2).to_a.sort)
+ assert_equal(@cls[[1,1,1],[1,1,2],[1,2,1],[1,2,2],
+ [2,1,1],[2,1,2],[2,2,1],[2,2,2]],
+ a.repeated_permutation(3).to_a.sort)
+ assert_equal(@cls[], a.repeated_permutation(-1).to_a)
+ assert_equal("abcde".each_char.to_a.repeated_permutation(5).sort,
+ "edcba".each_char.to_a.repeated_permutation(5).sort)
+ assert_equal(@cls[].repeated_permutation(0).to_a, @cls[[]])
+ assert_equal(@cls[].repeated_permutation(1).to_a, @cls[])
+
+ a = @cls[1, 2, 3, 4]
+ b = @cls[]
+ a.repeated_permutation {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
+ assert_equal(@cls[9, 8, 7, 6], a)
+ assert_equal(@cls[1, 2, 3, 4].repeated_permutation.to_a, b)
+ end
+
+ def test_repeated_combination
+ a = @cls[1,2,3]
+ assert_equal(@cls[[]], a.repeated_combination(0).to_a)
+ assert_equal(@cls[[1],[2],[3]], a.repeated_combination(1).to_a.sort)
+ assert_equal(@cls[[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]],
+ a.repeated_combination(2).to_a.sort)
+ assert_equal(@cls[[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
+ [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]],
+ a.repeated_combination(3).to_a.sort)
+ assert_equal(@cls[[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,2,2],[1,1,2,3],
+ [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
+ [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]],
+ a.repeated_combination(4).to_a.sort)
+ assert_equal(@cls[], a.repeated_combination(-1).to_a)
+ assert_equal("abcde".each_char.to_a.repeated_combination(5).map{|a|a.sort}.sort,
+ "edcba".each_char.to_a.repeated_combination(5).map{|a|a.sort}.sort)
+ assert_equal(@cls[].repeated_combination(0).to_a, @cls[[]])
+ assert_equal(@cls[].repeated_combination(1).to_a, @cls[])
+
+ a = @cls[1, 2, 3, 4]
+ b = @cls[]
+ a.repeated_combination {|x| b << x; a.replace(@cls[9, 8, 7, 6]) }
+ assert_equal(@cls[9, 8, 7, 6], a)
+ assert_equal(@cls[1, 2, 3, 4].repeated_combination.to_a, b)
+ end
+
def test_take
assert_equal([1,2,3], [1,2,3,4,5,0].take(3))
assert_raise(ArgumentError, '[ruby-dev:34123]') { [1,2].take(-1) }
combination_patch.txt
(2.47 KB, text/x-diff)
Index: array.c
===================================================================
--- array.c (revision 26886)
+++ array.c (working copy)
@@ -3976,11 +3976,14 @@
/*
* call-seq:
+ * ary.combination { |c| block } -> ary
+ * ary.combination -> enumerator
* ary.combination(n) { |c| block } -> ary
* ary.combination(n) -> enumerator
*
* 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.
+ * If <i>n</i> is not specified, yield all combinations of all elements.
* The implementation makes no guarantees about the order in which
* the combinations are yielded.
*
@@ -3989,6 +3992,7 @@
* Examples:
*
* a = [1, 2, 3, 4]
+ * a.combination.to_a #=> [[1, 2, 3, 4]]
* 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]]
@@ -3999,13 +4003,15 @@
*/
static VALUE
-rb_ary_combination(VALUE ary, VALUE num)
+rb_ary_combination(int argc, VALUE *argv, VALUE ary)
{
+ VALUE num;
long n, i, len;
- n = NUM2LONG(num);
- RETURN_ENUMERATOR(ary, 1, &num);
+ RETURN_ENUMERATOR(ary, argc, argv);
len = RARRAY_LEN(ary);
+ rb_scan_args(argc, argv, "01", &num);
+ n = NIL_P(num) ? len : NUM2LONG(num);
if (n < 0 || len < n) {
/* yield nothing */
}
@@ -4331,7 +4337,7 @@
rb_define_method(rb_cArray, "sample", rb_ary_sample, -1);
rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -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, "combination", rb_ary_combination, -1);
rb_define_method(rb_cArray, "product", rb_ary_product, -1);
rb_define_method(rb_cArray, "take", rb_ary_take, 1);
Index: test/ruby/test_array.rb
===================================================================
--- test/ruby/test_array.rb (revision 26886)
+++ test/ruby/test_array.rb (working copy)
@@ -1368,6 +1368,8 @@
assert_equal(@cls[[1,2,3],[1,2,4],[1,3,4],[2,3,4]], @cls[1,2,3,4].combination(3).to_a)
assert_equal(@cls[[1,2,3,4]], @cls[1,2,3,4].combination(4).to_a)
assert_equal(@cls[], @cls[1,2,3,4].combination(5).to_a)
+
+ assert_equal(@cls[1,2,3,4].combination(4).to_a, @cls[1,2,3,4].combination.to_a)
end
def test_product