diff options
author | marcandre <marcandre@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2010-04-07 17:36:15 +0000 |
---|---|---|
committer | marcandre <marcandre@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2010-04-07 17:36:15 +0000 |
commit | f3d2f9e4d13c6f871a5c72ebcadd1e0aeab267f3 (patch) | |
tree | 9e68029313b167ed78b2f13f444994a5acbea391 | |
parent | ceb62c31a1351422c208282a755d6eb3e0073a17 (diff) | |
download | ruby-f3d2f9e4d13c6f871a5c72ebcadd1e0aeab267f3.tar.gz |
* array.c (rb_ary_permutation): Remove limitation for lengthy permutations
[ruby-core:29240]
* test/ruby/test_array.rb: ditto
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@27252 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 7 | ||||
-rw-r--r-- | array.c | 27 | ||||
-rw-r--r-- | test/ruby/test_array.rb | 4 |
3 files changed, 13 insertions, 25 deletions
@@ -1,3 +1,10 @@ +Wed Apr 8 02:33:55 2010 Marc-Andre Lafortune <ruby-core@marc-andre.ca> + + * array.c (rb_ary_permutation): Remove limitation for lengthy permutations + [ruby-core:29240] + + * test/ruby/test_array.rb: ditto + Wed Apr 7 23:33:55 2010 KOSAKI Motohiro <kosaki.motohiro@gmail.com> * misc/ruby-mode.el (ruby-mode-map): binded C-c C-c and C-c C-c C-u @@ -3958,26 +3958,6 @@ rb_ary_permutation(int argc, VALUE *argv, VALUE ary) return ary; } -static long -combi_len(long n, long k) -{ - long i, val = 1; - - if (k*2 > n) k = n-k; - if (k == 0) return 1; - if (k < 0) return 0; - val = 1; - for (i=1; i <= k; i++,n--) { - long m = val; - val *= n; - if (val < m) { - rb_raise(rb_eRangeError, "too big for combination"); - } - val /= i; - } - return val; -} - /* * call-seq: * ary.combination(n) { |c| block } -> ary @@ -4024,14 +4004,13 @@ rb_ary_combination(VALUE ary, VALUE num) else { volatile VALUE t0 = tmpbuf(n+1, sizeof(long)); long *stack = (long*)RSTRING_PTR(t0); - long nlen = combi_len(len, n); volatile VALUE cc = tmpary(n); VALUE *chosen = RARRAY_PTR(cc); long lev = 0; MEMZERO(stack, long, n); stack[0] = -1; - for (i = 0; i < nlen; i++) { + for (;;) { chosen[lev] = RARRAY_PTR(ary)[stack[lev+1]]; for (lev++; lev < n; lev++) { chosen[lev] = RARRAY_PTR(ary)[stack[lev+1] = stack[lev]+1]; @@ -4041,9 +4020,11 @@ rb_ary_combination(VALUE ary, VALUE num) rb_raise(rb_eRuntimeError, "combination reentered"); } do { + if (lev == 0) goto done; stack[lev--]++; - } while (lev && (stack[lev+1]+n == len+lev+1)); + } while (stack[lev+1]+n == len+lev+1); } + done: tmpbuf_discard(t0); tmpary_discard(cc); } diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb index 6fc7fec48d..b2a42d5865 100644 --- a/test/ruby/test_array.rb +++ b/test/ruby/test_array.rb @@ -1842,8 +1842,8 @@ class TestArray < Test::Unit::TestCase end def test_combination2 - assert_raise(RangeError) do - (0..100).to_a.combination(50) {} + assert_nothing_raised do + (0..100).to_a.combination(50) { break } end end |