diff options
| -rw-r--r-- | array.c | 29 | ||||
| -rw-r--r-- | test/ruby/test_enumerator.rb | 5 |
2 files changed, 32 insertions, 2 deletions
@@ -26,7 +26,7 @@ VALUE rb_cArray; -static ID id_cmp; +static ID id_cmp, id_div; #define ARY_DEFAULT_SIZE 16 #define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE)) @@ -1539,6 +1539,9 @@ rb_ary_insert(int argc, VALUE *argv, VALUE ary) return ary; } +static VALUE +rb_ary_length(VALUE ary); + /* * call-seq: * ary.each { |item| block } -> ary @@ -4338,6 +4341,18 @@ descending_factorial(long from, long how_many) } static VALUE +binomial_coefficient(long comb, long size) +{ + if (comb > size-comb) { + comb = size-comb; + } + if (comb < 0) { + return LONG2FIX(0); + } + return rb_funcall(descending_factorial(size, comb), id_div, 1, descending_factorial(comb, comb)); +} + +static VALUE rb_ary_permutation_size(VALUE ary, VALUE args) { long n = RARRAY_LEN(ary); @@ -4414,6 +4429,15 @@ rb_ary_permutation(int argc, VALUE *argv, VALUE ary) return ary; } +static VALUE +rb_ary_combination_size(VALUE ary, VALUE args) +{ + long n = RARRAY_LEN(ary); + long k = NUM2LONG(RARRAY_PTR(args)[0]); + + return binomial_coefficient(k, n); +} + /* * call-seq: * ary.combination(n) { |c| block } -> ary @@ -4445,7 +4469,7 @@ rb_ary_combination(VALUE ary, VALUE num) long n, i, len; n = NUM2LONG(num); - RETURN_ENUMERATOR(ary, 1, &num); + RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_combination_size); len = RARRAY_LEN(ary); if (n < 0 || len < n) { /* yield nothing */ @@ -5237,4 +5261,5 @@ Init_Array(void) id_cmp = rb_intern("<=>"); sym_random = ID2SYM(rb_intern("random")); + id_div = rb_intern("div"); } diff --git a/test/ruby/test_enumerator.rb b/test/ruby/test_enumerator.rb index a4222f2ac0..90718b29cb 100644 --- a/test/ruby/test_enumerator.rb +++ b/test/ruby/test_enumerator.rb @@ -441,6 +441,11 @@ class TestEnumerator < Test::Unit::TestCase assert_equal 24, [0, 1, 2, 4].permutation.size assert_equal 2933197128679486453788761052665610240000000, (1..42).to_a.permutation(30).size # 1.upto(42).inject(:*) / 1.upto(12).inject(:*) + + check_consistency_for_combinatorics(:combination) + assert_equal 28258808871162574166368460400, + (1..100).to_a.combination(42).size + # 1.upto(100).inject(:*) / 1.upto(42).inject(:*) / 1.upto(58).inject(:*) end end |