ruby-core

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

Attachments (1)

diffs (6.61 KB, text/x-diff)

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 = 1;
+/*
+ * 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 = 0; i < n; i++) {
+	if (used[i] == 0) {
+	    p[index] = i;
+	    if (index < r-1) {             /* if not done yet */
+		used[i] = 1;               /* mark index used */
+		permute0(n,r,p,index+1,    /* recurse */
+			 used, values);  
+		used[i] = 0;               /* 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 = rb_ary_new2(r);
+		VALUE *result_array = RARRAY_PTR(result);
+		VALUE *values_array = RARRAY_PTR(values);
 
-    while (n > k) {
-	val *= n--;
+		for(j = 0; j < r; j++) result_array[j] = values_array[p[j]];
+		RARRAY(result)->len = r;
+		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 = NUM2LONG(num);           /* Permutation size from argument */
+    long n = RARRAY_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 = 0; i < RARRAY_LEN(ary); i++) {
+	    rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
+	}
+    }
+    else {             /* this is the general case */
+	ary = rb_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 = 0; i < n; i++) used[i] = 0; /* 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 = NUM2LONG(num);
     len = RARRAY_LEN(ary);
-    if (len < n) {
+    if (n < 0 || len < n) {
 	/* yield nothing */
     }
-    else if (n <= 0) {
+    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

Thread

Prev Next

In This Thread

Prev Next

[#12312] Need Japanese Help - VRuby & new One-Click Ruby Installer with patch 110 — "Curt Hibbs" <curt.hibbs@...>

[#12328] Dir.chdir patch for MS Windows — "Berger, Daniel" <Daniel.Berger@...>

[#12336] Re: gc.c -- possible logic error? — Brent Roman <brent@...>

[#12338] gc.c refactoring — Hugh Sasse <hgs@...>

[#12344] patch to implement Array.permutation — David Flanagan <david@...>

[#12346] a patch for Array.permutation and a generalization of Array.product — David Flanagan <david@...>

[#12351] ruby19 omits program name for missing files — Eric Hodel <drbrain@...7.net>

[#12352] system and Errno::ENOENT in 1.9 — Eric Hodel <drbrain@...7.net>

[#12371] Bug 6400: Time#+ and Time#- not honoring subclass — "Ron Leisti" <ron.leisti@...>

[#12372] Release compatibility/train — Prashant Srinivasan <Prashant.Srinivasan@...>

[#12375] some typos in doc/comments in repos/ruby/trunk — Eugene Ossintsev <eugoss@...>

[#12379] discrepancy between String#oct and String#hex — Ryan Davis <ryand-ruby@...>

[#12383] Include Rake in Ruby 1.9 — "NAKAMURA, Hiroshi" <nakahiro@...>

[#12401] tIDENTIFIER and is_local_id() — Thomas Enebo <Thomas.Enebo@...>

[#12404] ruby-1.9 build Sun-sparc-solaris2.9 — Hugh Sasse <hgs@...>

[#12411] rdoc patch — David Flanagan <david@...>

[#12412] REXML + RSS — Sean Russell <ser@...>

[#12414] Performance Issues with nil, true, false as Hash Keys (1.8.6) — =?ISO-8859-15?Q?Matthias_W=E4chter?= <matthias@...>

[#12418] Patch for configure.in — "Richard Brown" <rbrown@...>

[#12529] Re: Compile error for HEAD — "NARUSE, Yui" <naruse@...>

[#12533] Quick Enumerable#sort_by internals question — Daniel Berger <Daniel.Berger@...>

[#12537] Re: Why does def return nil? — "Jonas Pfenniger" <zimbatm@...>

[#12539] Ordered Hashes in 1.9? — Michael Neumann <mneumann@...>

[#12540] Re: Why does def return nil? — "Jonas Pfenniger" <zimbatm@...>

[#12547] Bug in win32ole — "Waters, Chris" <cwaters@...>

[#12550] to let Ruby 1.9 to process signals while blocked in ext/readline — Brent Roman <brent@...>

[#12564] Re: net/http.rb, patch, possible bug, test problem — Hugh Sasse <hgs@...>

[#12566] Revised net/http patch — Hugh Sasse <hgs@...>

[#12568] $" and require — "Tim Morgan" <tmorgan99@...>

[#12573] File::Stat#grpowned? is wrong — Bertram Scharpf <lists@...>

[#12575] Marshal.dump doesn't dump string encoding — David Flanagan <david@...>

[#12578] Possible memory leak in ruby-1.8.6-p110?? — "M. Edward (Ed) Borasky" <znmeb@...>

[#12579] iconv enhancement in Ruby 1.9 — "Eugene Ossintsev" <eugoss@...>

[#12581] ruby.exe exit code 255 — "Drew Sears" <dsears@...>

[#12584] Broken Ruby/ODBC due rbconfig COMMON_MACROS — "Luis Lavena" <luislavena@...>

[#12587] Confusion about arities — Charles Oliver Nutter <charles.nutter@...>

[#12588] MatchData#select rdoc and arity incorrect — Charles Oliver Nutter <charles.nutter@...>

[#12598] adds __file__ and __line__ methods to Methods and Procs — Brent Roman <brent@...>

[#12599] private method dispatch changes dropped from 1.9? — David Flanagan <david@...>

[#12610] Re: Release compatibility/train — Yukihiro Matsumoto <matz@...>

[#12615] Re: Why does def return nil? — Brent Roman <brent@...>

[#12617] Question about heap_slots in gc.c — Hongli Lai <h.lai@...>

[#12618] StringIO is not IO? — Hongli Lai <h.lai@...>

[#12623] Behaviour of String Objects - Why Not "Each" for Characters and Enumerable? — =?ISO-8859-15?Q?Wolfgang_N=E1dasi-Donner?= <ed.odanow@...>

[#12629] file encoding comments and a patch to parse.y — David Flanagan <david@...>

[#12632] Defining unicode methods — "Daniel Berger" <djberg96@...>

[#12636] Proc.yield method — David Flanagan <david@...>

[#12638] New lambda -> syntax — David Flanagan <david@...>

[#12639] test problem after compiling — Martin Duerst <duerst@...>

[#12664] minor rdoc patch to encoding.c — David Flanagan <david@...>

[#12665] Another encoding.c patch — David Flanagan <david@...>

[#12666] encoding.c bug — David Flanagan <david@...>

[#12670] Bug in Numeric#divmod — "Dirk Traulsen" <dirk.traulsen@...>

[#12675] Re: Import gem to Ruby 1.9 — Brent Roman <brent@...>

[#12676] Minor Array.shuffle patch — David Flanagan <david@...>

[#12679] documentation patch for enum.c — David Flanagan <david@...>

[#12681] Unicode: Progress? — murphy <murphy@...>

[#12693] retry: revised 1.9 http patch — Hugh Sasse <hgs@...>

[#12695] New Rails plugin 'Liftoff' is available. — "Ben Tompkins" <nbitspoken@...>

[#12697] Range.first is incompatible with Enumerable.first — David Flanagan <david@...>

[#12703] Long encoding names with -K and bad error message — David Flanagan <david@...>

[#12705] A couple of bugs? — "John Lam (DLR)" <jflam@...>

[#12706] Re: A couple of bugs? — "Gavin Kistner" <gavin.kistner@...>

[#12710] enum.c patch: fixes Enumerable.cycle and rdoc bugs — David Flanagan <david@...>

[#12714] Re: A couple of bugs? — "Gavin Kistner" <gavin.kistner@...>

[#12750] Re: [OT] Re: Should *most* memory be release back to the system? — "M. Edward (Ed) Borasky" <znmeb@...>

[#12754] Improving 'syntax error, unexpected $end, expecting kEND'? — Hugh Sasse <hgs@...>

[#12757] Re: Unicode: Progress?? — Brent Roman <brent@...>

[#12758] Encoding::primary_encoding — David Flanagan <david@...>

[#12759] Reading UTF-8 Data contains BOM — =?ISO-8859-15?Q?Wolfgang_N=E1dasi-Donner?= <ed.odanow@...>

[#12764] SystemStackError 1.8.6 (stack only 25 frames) — Dan Janowski <danj@3skel.com>

[#12767] \u escapes in string literals: proof of concept implementation — David Flanagan <david@...>

[#12776] Clarification of Ruby release plans? 1.8.7? 1.9.1? 2.0? — Lucas Nussbaum <lucas@...>

[#12779] Re: Unicode: Progress?? — Brent Roman <brent@...>

[#12780] Re: Unicode: Progress?? — Brent Roman <brent@...>

[#12787] How to specify in Ruby 1.9 the expected file encoding — =?ISO-8859-15?Q?Wolfgang_N=E1dasi-Donner?= <ed.odanow@...>

[#12795] patch for String.concat — David Flanagan <david@...>

[#12825] clarification of ruby libraries installation paths? — Lucas Nussbaum <lucas@...>

[#12834] Bug Tracker Access Request — James Edward Gray II <james@...>

[#12847] make test-all — "Florian Ebeling" <florian.ebeling@...>

[#12598] adds file and line methods to Methods and Procs — Brent Roman <brent@...>

[#12750] Re: [OT] Re: Should most memory be release back to the system? — "M. Edward (Ed) Borasky" <znmeb@...>