Project

General

Profile

Feature #2981

Array#repeated_(permutation|combination)

Added by metanest (Makoto Kishimoto) almost 10 years ago. Updated over 8 years ago.

Status:
Closed
Priority:
Normal
Target version:
[ruby-core:28724]

Description

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

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

Attachment: repeated_patch.txt
=end


Files

repeated_patch.txt (10.3 KB) repeated_patch.txt patch metanest (Makoto Kishimoto), 04/06/2010 09:04 AM

Associated revisions

Revision d49860bf
Added by kazu almost 10 years ago

NEWS: add Array#repeated_{combinationpermutation} [Feature #2981]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@27369 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 27369
Added by kazu almost 10 years ago

NEWS: add Array#repeated_{combinationpermutation} [Feature #2981]

Revision 27369
Added by znz (Kazuhiro NISHIYAMA) almost 10 years ago

NEWS: add Array#repeated_{combinationpermutation} [Feature #2981]

Revision 27369
Added by kazu almost 10 years ago

NEWS: add Array#repeated_{combinationpermutation} [Feature #2981]

Revision 27369
Added by kazu almost 10 years ago

NEWS: add Array#repeated_{combinationpermutation} [Feature #2981]

Revision 27369
Added by kazu almost 10 years ago

NEWS: add Array#repeated_{combinationpermutation} [Feature #2981]

Revision 27369
Added by kazu almost 10 years ago

NEWS: add Array#repeated_{combinationpermutation} [Feature #2981]

History

#1

Updated by naruse (Yui NARUSE) almost 10 years ago

=begin
Show use case.
=end

#2

Updated by shyouhei (Shyouhei Urabe) almost 10 years ago

=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

#3

Updated by metanest (Makoto Kishimoto) almost 10 years ago

=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(@cls1],[2, a.repeated_permutation(1).to_a.sort)

  • assert_equal(@cls1,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(@cls1],[2],[3, a.repeated_combination(1).to_a.sort)

  • assert_equal(@cls1,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

#4

Updated by metanest (Makoto Kishimoto) almost 10 years ago

=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

#5

Updated by metanest (Makoto Kishimoto) almost 10 years ago

=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

#6

Updated by mame (Yusuke Endoh) almost 10 years ago

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

=end

#7

Updated by naruse (Yui NARUSE) almost 10 years ago

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

=begin

=end

#8

Updated by znz (Kazuhiro NISHIYAMA) almost 10 years ago

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

=begin

=end

#9

Updated by metanest (Makoto Kishimoto) almost 10 years ago

=begin
patch for current trunk
=end

#10

Updated by matz (Yukihiro Matsumoto) almost 10 years ago

  • 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

Also available in: Atom PDF