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

On Thu, 12 Apr 2007 15:08:09 +0000, Ken Bloom wrote:

> 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

FYI, since this is a derived work from the G++ STL, it's under the GNU 
General Public license, version 2 or (at your option) any later version.

> 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/