From: Ken Bloom <kbloom@...>
Date: 2007-04-13T00:10:10+09:00
Subject: next_permutation (was Re: [QUIZ] Counting to 100 (#119))

On Wed, 11 Apr 2007 03:08:07 +0000, Ken Bloom wrote:

> On Wed, 11 Apr 2007 10:55:07 +0900, Erwin Abbott wrote:
> 
>> It would be really interesting to write a non-recursive permute
>> function that could map a number n to each permutation of digits, and
>> map n+1 to the next permutation.  Then we could just count from 1 to
>> 6561 for 9 digits, 1 to 19683 for 10 digits, etc.  Something like this:
>>   permutation(1, 1..9) => [1, 2, 3, 4, 5, 6, 7, 8, 9] permutation(6549,
>>   1..9) => [123456, 78, 9] permutation(6560, 1..9) => [123456, 789]
>> 
>> This is easy when we're permuting a single number (it's just converting
>> to another base), but it might not be possible in this problem.  I
>> guess the recursive method really only goes 9 or 10 level deep anyway.
> 
> This isn't permuting -- it's partitioning. Permuting is coming up with
> all possible orders for the elements in the array.
> 
> Although it brings up a point that I find interesting -- most of the
> permutation generator implementations I've seen for Ruby are recursive
> -- they do very specific things with the positions in the array without
> regard to what the contents are. This causes issues like duplicate
> permutations when there are duplicate elements in the array.
> 
> Is there an implementation of a permutation generator out there that
> works similar to the C++ STL's next_permutation function? The C++ STL's
> next_permutation function doesn't have the luxury of recursion or state,
> so it has to generate permutations based on the ordering of elements
> according to the comparison operators.

OK. Here we go. I've ported this from the G++ 4.1 STL, which can be found 
in /usr/include/c++/4.1.2/bits/stl_algo.h


class Array
   #based on the C++ standard library's implementation
   def next_permutation!
      return self if length<2
      i=length-1
      while true
	 ii=i
	 i-=1
	 if self[i]<self[ii]
	    j=length
	    nil until self[i]<self[j-=1]
	    self[i],self[j]=self[j],self[i]
	    reverse_part!(ii,length)
	    return self
	 end
	 if (i == 0)
	    reverse!
	    return self
	 end
      end
   end

   def next_permutation
      dup.next_permutation!
   end

   def reverse_part! start,stop
      while start<stop
	 self[start],self[stop-1]=self[stop-1],self[start]
	 stop-=1
	 start+=1
      end
   end
   private :reverse_part!

   #each_permutation implementation that permutes based on
   #the contents of the array. No duplicate permutations are
   #yielded, even when there are duplicate elements in
   #the array. The elements of the array must
   #be mutually comparable. 
   def each_permutation
      temp=sort
      stop=temp.reverse
      yield temp
      until temp.next_permutation! == stop
	 yield temp
      end
   end
end

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/