diff options
author | matz <matz@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2007-10-02 03:33:53 +0000 |
---|---|---|
committer | matz <matz@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2007-10-02 03:33:53 +0000 |
commit | 77a6c82eabe113802a52bf77b8b8a0bcfe1f28f4 (patch) | |
tree | 7083bfd19e3e75315c569478e0a809774c93f6ff | |
parent | 437565235f3bae03cfed4afbf9902ca96adb3252 (diff) | |
download | ruby-77a6c82eabe113802a52bf77b8b8a0bcfe1f28f4.tar.gz |
* array.c (rb_ary_product): generalized product, now takes
arbitrary number of arrays. a patch from David Flanagan
<david AT davidflanagan.com>. [ruby-core:12346]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@13598 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 6 | ||||
-rw-r--r-- | array.c | 72 | ||||
-rw-r--r-- | test/ruby/test_array.rb | 6 |
3 files changed, 70 insertions, 14 deletions
@@ -1,3 +1,9 @@ +Tue Oct 2 12:30:40 2007 Yukihiro Matsumoto <matz@ruby-lang.org> + + * array.c (rb_ary_product): generalized product, now takes + arbitrary number of arrays. a patch from David Flanagan + <david AT davidflanagan.com>. [ruby-core:12346] + Tue Oct 2 08:25:50 2007 Yukihiro Matsumoto <matz@ruby-lang.org> * array.c (rb_ary_permutation): implementation contributed from @@ -2967,7 +2967,8 @@ rb_ary_cycle(VALUE ary) * 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) { +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) { @@ -3132,30 +3133,73 @@ rb_ary_combination(VALUE ary, VALUE num) /* * call-seq: - * ary.product(ary2) + * ary.product(other_ary, ...) * - * Returns an array of all combinations of elements from both arrays. - * - * [1,2,3].product([4,5]) #=> [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]] - * [1,2].product([1,2]) #=> [[1,1],[1,2],[2,1],[2,2]] + * Returns an array of all combinations of elements from all arrays. + * The length of the returned array is the product of the length + * of ary and the argument arrays * + * [1,2,3].product([4,5]) # => [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]] + * [1,2].product([1,2]) # => [[1,1],[1,2],[2,1],[2,2]] + * [1,2].product([3,4],[5,6]) # => [[1,3,5],[1,3,6],[1,4,5],[1,4,6], + * # [2,3,5],[2,3,6],[2,4,5],[2,4,6]] + * [1,2].product() # => [[1],[2]] + * [1,2].product([]) # => [] */ static VALUE -rb_ary_product(VALUE ary, VALUE a2) +rb_ary_product(int argc, VALUE *argv, VALUE ary) { - VALUE result = rb_ary_new2(RARRAY_LEN(ary)); - long i, j; + int n = argc+1; /* How many arrays we're operating on */ + VALUE arrays[n]; /* The arrays we're computing the product of */ + int counters[n]; /* The current position in each one */ + VALUE result; /* The array we'll be returning */ + long i,j; - for (i=0; i<RARRAY_LEN(ary); i++) { - for (j=0; j<RARRAY_LEN(a2); j++) { - rb_ary_push(result, rb_ary_new3(2, rb_ary_entry(ary, i), - rb_ary_entry(a2, j))); + /* initialize the arrays of arrays */ + arrays[0] = ary; + for(i = 1; i < n; i++) arrays[i] = argv[i-1]; + + /* initialize the counters for the arrays */ + for(i = 0; i < n; i++) counters[i] = 0; + + /* Compute the length of the result array; return [] if any is empty */ + long resultlen = 1; + for(i = 0; i < n; i++) { + resultlen *= RARRAY_LEN(arrays[i]); + if (resultlen == 0) return rb_ary_new2(0); + } + + /* Otherwise, allocate and fill in an array of results */ + result = rb_ary_new2(resultlen); + for(i = 0; i < resultlen; i++) { + /* fill in one subarray */ + VALUE subarray = rb_ary_new2(n); + for(j = 0; j < n; j++) { + rb_ary_push(subarray, rb_ary_entry(arrays[j], counters[j])); + } + + /* put it on the result array */ + rb_ary_push(result, subarray); + + /* + * Increment the last counter. If it overflows, reset to 0 + * and increment the one before it. + */ + int m = n-1; + counters[m]++; + while(m >= 0 && counters[m] == RARRAY_LEN(arrays[m])) { + counters[m] = 0; + m--; + counters[m]++; } } + return result; } + + /* Arrays are ordered, integer-indexed collections of any object. * Array indexing starts at 0, as in C or Java. A negative index is * assumed to be relative to the end of the array---that is, an index of -1 @@ -3256,7 +3300,7 @@ Init_Array(void) 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, "combination", rb_ary_combination, 1); - rb_define_method(rb_cArray, "product", rb_ary_product, 1); + rb_define_method(rb_cArray, "product", rb_ary_product, -1); id_cmp = rb_intern("<=>"); } diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb index 2e9c6fca57..6787d9c99c 100644 --- a/test/ruby/test_array.rb +++ b/test/ruby/test_array.rb @@ -1190,6 +1190,12 @@ class TestArray < Test::Unit::TestCase assert_equal(@cls[[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]], @cls[1,2,3].product([4,5])) assert_equal(@cls[[1,1],[1,2],[2,1],[2,2]], @cls[1,2].product([1,2])) + + assert_equal(@cls[[1,3,5],[1,3,6],[1,4,5],[1,4,6], + [2,3,5],[2,3,6],[2,4,5],[2,4,6]], + @cls[1,2].product([3,4],[5,6])) + assert_equal(@cls[[1],[2]], @cls[1,2].product) + assert_equal(@cls[], @cls[1,2].product([])) end def test_permutation |