Feature #2981: Array#repeated_(permutation|combination)

• Status: Closed
• Assignee: matz (Yukihiro Matsumoto)
• Target version: 1.9.2

[metanest (Makoto Kishimoto)]

=begin
New methods Array#repeated_(permutation|combination).

Like Array#(permutation|combination), these methods make
repeated permutation or combination.

Attachment: repeated_patch.txt
=end

[naruse (Yui NARUSE)]

=begin
Show use case.
=end

[shyouhei (Shyouhei Urabe)]

=begin
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.
=end

[metanest (Makoto Kishimoto)]

=begin
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
• • n of the elements of ary, 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 n of elements from ary and then returns
• • ary 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) }

=end

[metanest (Makoto Kishimoto)]

=begin
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
}

=end

[metanest (Makoto Kishimoto)]

=begin
(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

=end

[mame (Yusuke Endoh)]

=begin
Hi matz,

2010/3/18 KISHIMOTO, Makoto [e-mail]:

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 [e-mail]

=end

[naruse (Yui NARUSE)]

• Category set to core
• Status changed from Open to Assigned
• Assignee set to matz (Yukihiro Matsumoto)
• Priority changed from 3 to Normal

=begin

=end

[znz (Kazuhiro NISHIYAMA)]

• Target version set to 1.9.2
• Start date set to 03/18/2010

=begin

=end

[metanest (Makoto Kishimoto)]

• File repeated_patch.txt repeated_patch.txt added

=begin
patch for current trunk
=end

[matz (Yukihiro Matsumoto)]

• Status changed from Assigned to Closed
• % Done changed from 0 to 100

=begin
This issue was solved with changeset r27352.
Makoto, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end