Ruby » ruby-trunk

Show use case.

A bit more: use cases are shown in Japanese ML (and I think they're OK), so please just translate them for non-Japanese speakers.

Sorry, the patch of [ruby-core:28724] has bug.

This is fixed version.

Index: array.c
===================================================================
--- array.c	(revision 26970)
+++ array.c	(working copy)
@@ -4047,7 +4047,187 @@
 }

 /*
+ * 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(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.
+ * 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(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(VALUE ary, VALUE num)
+{
+    long r, n, i;
+
+    n = RARRAY_LEN(ary);                  /* Array length */
+    RETURN_ENUMERATOR(ary, 1, &num);      /* Return enumerator if no block */
+    r = 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(r, 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(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(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(VALUE ary, VALUE num)
+{
+    long n, i, len;
+
+    n = NUM2LONG(num);                 /* Combination size from argument */
+    RETURN_ENUMERATOR(ary, 1, &num);   /* Return enumerator if no block */
+    len = RARRAY_LEN(ary);
+    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 +4512,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 26970)
+++ 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(2) {
+        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(2) {
+        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(4) {|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(4).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(4) {|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(4).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) }

An example of number puzzle.

['+', '-', '*', '/', ''].repeated_permutation(8).each{|a, b, c, d, e, f, g, h|
	s = "1#{a}2#{b}3#{c}4#{d}5#{e}6#{f}7#{g}8#{h}9"
	n = eval s
	if n == 100 then
		p s
	end
}

(from [ruby-dev:40601] )

Try to login with too short passwords.

("a".."z").to_a.repeated_permutation(5).find {|s| login(s.join) }

====

Check ruby parser with doubtful strings.

%w(( ) $ ` ' | & =).repeated_permutation(5) do |s|
    begin; eval(p(s.join)); rescue Exception; end
end

Hi matz,

2010/3/18 KISHIMOTO, Makoto <ksmakoto@dd.iij4u.or.jp>:
> New methods Array#repeated_(permutation|combination).
>
> Like Array#(permutation|combination), these methods make
> repeated permutation or combination.


You have already approved this feature at [ruby-dev:40610], and
you said you would apply the patch.

Could you, or may I commit the patch?

-- 
Yusuke ENDOH <mame@tsg.ne.jp>