This is a multi-part message in MIME format.
--------------080505070205090803040504
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hi,

The attached patch implements Array.permutation.  Matz's change log when 
he checked in the stub for this method invited volunteers to implement 
it, so I've taken a stab at it.

This is my first non-trivial patch, and its been a long time since I did 
any serious C coding, so please check my code.

This patch also includes an update to the documentation for 
Array.permutation and Array.combination.   And a minor change to 
Array.combination: combination(0) was yielding nothing rather than 
yielding the single value 0.

Also, I've added a test case to test/ruby/test_array.c

	David

--------------080505070205090803040504
Content-Type: text/plain;
 name
iffs"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename
iffs"

Index: array.c
--- array.c	(revision 13588)
+++ array.c	(working copy)
@@ -2954,37 +2954,95 @@
     return Qnil;
 }
 
-static long
-perm_len(long n, long k)
-{
-    long i, val  ;
+/*
+ * Recursively compute permutations of r elements of the set [0..n-1].
+ * When we have a complete 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
+ * used: an array of booleans: whether a given index is already used
+ * 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) {
+    long i,j;
+    for(i  ; i < n; i++) {
+	if (used[i] 0) {
+	    p[index]  ;
+	    if (index < r-1) {             /* if not done yet */
+		used[i]  ;               /* mark index used */
+		permute0(n,r,p,index+1,    /* recurse */
+			 used, values);  
+		used[i]  ;               /* index unused */
+	    }
+	    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  b_ary_new2(r);
+		VALUE *result_array  ARRAY_PTR(result);
+		VALUE *values_array  ARRAY_PTR(values);
 
-    while (n > k) {
-	val * --;
+		for(j  ; j < r; j++) result_array[j]  alues_array[p[j]];
+		RARRAY(result)->len  ;
+		rb_yield(result);
+	    }
+	}
     }
-    return val;
 }
 
 /*
  *  call-seq:
- *     ary.permutation(n)
+ *     ary.permutation(n) { |p| block }       -> array
+ *     ary.permutation(n)                     -> enumerator
  *  
- *  Returns an array of all permutations of length <i>n</i> of
- *  elements from <i>ary</i>].
- *     
+ * When invoked with a block, yield all permutations of length <i>n</i>
+ * of the elements of <i>ary</i>, then return the array itself.
+ * The implementation makes no guarantees about the order in which 
+ * the permutations are yielded.
+ *
+ * When invoked without a block, return an enumerator object instead.
+ * 
+ * Examples:
  *     a  1, 2, 3]
- *     a.permutation(0).to_a  #[]
  *     a.permutation(1).to_a  #[[1],[2],[3]]
  *     a.permutation(2).to_a  #[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
  *     a.permutation(3).to_a  #[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
- *     a.permutation(4).to_a  #[]
- *     
+ *     a.permutation(0).to_a  #[[]]: one permutation of length 0
+ *     a.permutation(4).to_a  #[]  : no permutations of length 4
  */
 
 static VALUE
 rb_ary_permutation(VALUE ary, VALUE num)
 {
-    /* TBD */
+    RETURN_ENUMERATOR(ary, 1, &num);  /* Return enumerator if no block */
+    long r  UM2LONG(num);           /* Permutation size from argument */
+    long n  ARRAY_LEN(ary);         /* Array length */
+    long i;
+
+    if (r < 0 || n < r) { 
+	/* 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  ; i < RARRAY_LEN(ary); i++) {
+	    rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
+	}
+    }
+    else {             /* this is the general case */
+	ary  b_ary_dup(ary); /* private defensive copy of ary */
+	long p[r];              /* array indexes of current permutation */
+	int used[n];           /* booleans: which indexes are already used */
+	for(i  ; i < n; i++) used[i]  ; /* initialize array */
+
+	permute0(n,r,p,0,used,ary);  /* compute and yield permutations */
+    }
+    return ary;
 }
 
 static long
@@ -3005,18 +3063,24 @@
 
 /*
  *  call-seq:
- *     ary.combination(n)
+ *     ary.combination(n) { |c| block }    -> ary
+ *     ary.combination(n)                  -> enumerator
  *  
- *  Returns an enumerator of all combinations of length <i>n</i> of
- *  elements from <i>ary</i>].
+ * When invoked with a block, yields all combinations of length <i>n</i> 
+ * of elements from <i>ary</i> and then returns <i>ary</i> itself.
+ * The implementation makes no guarantees about the order in which 
+ * the combinations are yielded.
+ *
+ * When invoked without a block, returns an enumerator object instead.
  *     
+ * Examples:
  *     a  1, 2, 3, 4]
- *     a.combination(0).to_a  #[]
  *     a.combination(1).to_a  #[[1],[2],[3],[4]]
  *     a.combination(2).to_a  #[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
  *     a.combination(3).to_a  #[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
  *     a.combination(4).to_a  #[[1,2,3,4]]
- *     a.combination(5).to_a  #[]
+ *     a.combination(0).to_a  #[[]]: one combination of length 0
+ *     a.combination(5).to_a  #[]  : no combinations of length 5
  *     
  */
 
@@ -3028,10 +3092,10 @@
     RETURN_ENUMERATOR(ary, 1, &num);
     n  UM2LONG(num);
     len  ARRAY_LEN(ary);
-    if (len < n) {
+    if (n < 0 || len < n) {
 	/* yield nothing */
     }
-    else if (n < ) {
+    else if (n 0) {
 	rb_yield(rb_ary_new2(0));
     }
     else if (n 1) {
@@ -3187,7 +3251,7 @@
     rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, 0);
     rb_define_method(rb_cArray, "choice", rb_ary_choice, 0);
     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, "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);
 
Index: test/ruby/test_array.rb
--- test/ruby/test_array.rb	(revision 13588)
+++ test/ruby/test_array.rb	(working copy)
@@ -1199,4 +1199,20 @@
                  @cls[1,2,3].product([4,5]))
     assert_equal(@cls[[1,1],[1,2],[2,1],[2,2]], @cls[1,2].product([1,2]))
   end
+
+  def test_permutation
+    a  cls[1,2,3]
+    assert_equal(@cls[[]], a.permutation(0).to_a)
+    assert_equal(@cls[[1],[2],[3]], a.permutation(1).to_a.sort)
+    assert_equal(@cls[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]],
+                 a.permutation(2).to_a.sort)
+    assert_equal(@cls[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]],
+                 a.permutation(3).sort.to_a)
+    assert_equal(@cls[], a.permutation(4).to_a)
+    assert_equal(@cls[], a.permutation(-1).to_a)
+    assert_equal("abcde".each_char.to_a.permutation(5).sort,
+                 "edcba".each_char.to_a.permutation(5).sort)
+    assert_equal(@cls[].permutation(0).to_a, @cls[[]])
+
+  end
 end

--------------080505070205090803040504--