From: "Mehr, Assaph (Assaph)" <assaph@...>
Date: 2004-07-19T15:11:47+09:00
Subject: Re: Another little algoritmic help needed...

> Building all permutations of something is a typical recursive task.
> But in this case I dont want a recursive solution because:


There's a non-recursive permutation algorithm at:
http://www.geocities.com/permute_it/

Here is an implementation I once made:


class Array
    def swap!(idx1, idx2)
        if (idx1.abs > self.length || idx2.abs > self.length )
            raise ArgumentError.new("non valid indices!")
        end
        
        a = self[idx1]
        self[idx1] = self[idx2]
        self[idx2] = a
        self
    end
end
        

# algorithm by: http://www.geocities.com/permute_it/
class Permutations
    def initialize(ary)
        if (not ary.kind_of?(Array) or ary.empty?)
            raise ArgumentError.new("ary should be a non-empty Array!")
        end
        @ary = ary.sort
        @n = ary.length
        @pary = (0..@n+1).to_a
        @i = 1
        @first = true
    end
    
    attr_reader :ary, :i
    
    def next

        if not @first
            raise StandardError, "Permutations Exhausted!" if @i >= @n
    
            @pary[i] -= 1
            j = (i%2 == 0 ? 0 : @pary[i]) # if i is odd, then let j =
p[i] otherwise let j = 0
            @ary.swap!(i, j)
            @i = 1
            while (@pary[i] == 0)
                @pary[i] = @i
                @i += 1
            end # end while (p[i] is equal to 0)
        else
            @first = false
        end

        if block_given?        
            yield ary
        end
        ary
    end

    def hasNext?
        @i < @n
    end
    
    def reset
        @ary = ary.sort
        @n = ary.length
        @pary = (0..n+1).to_a
        @i = 1
    end
    
    def Permutations.go(array)
        if ( not array.kind_of?(Array) or array.empty?)
            raise ArgumentError.new("ary should be a non-empty Array!")
        end
        ary = array.sort
        n = ary.length
        pary = (0..n+1).to_a

        i = 1
        while (i < n)
            yield ary
            pary[i] -= 1
            j = (i%2 == 0 ? 0 : pary[i]) # if i is odd, then let j =
p[i] otherwise let j = 0
            ary.swap!(i, j)
            i = 1
            while (pary[i] == 0)
                pary[i] = i
                i += 1
            end # end while (p[i] is equal to 0)
        end # end while (i < N)
        yield ary
   end
end