marcandre	2012-11-07 02:11:21 +0900 (Wed, 07 Nov 2012)

  New Revision: 37502

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=37502

  Log:
    * array.c (rb_ary_combination): Support for Array#combination.size
      [Feature #6636]

  Modified files:
    trunk/array.c
    trunk/test/ruby/test_enumerator.rb

Index: array.c
===================================================================
--- array.c	(revision 37501)
+++ array.c	(revision 37502)
@@ -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 @@
     return ary;
 }
 
+static VALUE
+rb_ary_length(VALUE ary);
+
 /*
  *  call-seq:
  *     ary.each { |item| block }  -> ary
@@ -4338,6 +4341,18 @@
 }
 
 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 @@
     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 @@
     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 @@
 
     id_cmp = rb_intern("<=>");
     sym_random = ID2SYM(rb_intern("random"));
+    id_div = rb_intern("div");
 }
Index: test/ruby/test_enumerator.rb
===================================================================
--- test/ruby/test_enumerator.rb	(revision 37501)
+++ test/ruby/test_enumerator.rb	(revision 37502)
@@ -441,6 +441,11 @@
     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
 

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/