From: Daniel Sheppard <daniels@...>
Date: 2005-11-03T13:32:30+09:00
Subject: Fun with Permutations

For a little project I've been doing, I've been playing around with
permutations of arrays, and came across a couple of interesting methods
that might want to find their way into facets or one of those other
libraries that are floating around. I'm not sure if it has any
application outside of trying to save disk/memory space, but here goes.

Part of what I want to do involves storing information about all the
different permutations of an array - the problem with this is that I'm
writing the same data repeatedly, just in different orderings. Take for
example, an array of 4 integers, sorted into all the permutations:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
..
[4, 2, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]

There's the same array 24 different times. Instead, using my new magic
"permutation_number" and "permute" methods, a unique number between 0
and 23 can be assigned to each sort ordering and that can be stored
instead. So, instead of storing "N! * N * fields" bytes, I only need to
store "N! * integers + N * fields". I can also seek into a binary file
based on the sort key to pull out data... which is nice. I don't know if
there's some famous mathematical formula that proves this, that gives
these methods a better name, or if they should be called "sort_key" and
"sort_by_key" or something.

class Array  
    def permute(number)
        out = self[0..0]
        nextfactor = factor = 1
        each_with_index {|x,i|
            case i
                when 0: next
                else 
                    nextfactor = factor * (i+1)
                    out.insert(number % nextfactor / factor, x)
                    factor = nextfactor
            end
        }        
        out
    end
    def permutation_number(original_array=self.sort)
        m = 1
        v = 0
        last_indicies = Hash.new(0)
        original_array.each_with_index {|x,i|
            next if i==0
            m *= i
            done = original_array[0..i]
            v += m * self.select {|y| done.include?(y)}.rindex(x)
        }
        v
    end
end

[3,1,2,4].permutation_number
=> 19
[1,2,3,4].permute(19)
=> [4,3,2,1]

It basically works by building up an array from the original. There is 1
place for the first item, 2 available for the second, 3 for the third,
etc. So, if you look at the number 19:

3 * 3! = 18, leaves 1
0 * 2! = 0, leaves 1
1 * 1! = 1, leaves 0

so we then build up the array, starting with [1].
We insert the next item at position 1, giving [1,2]
we insert the next item at position 0, giving [3,1,2]
we insert the next item at position 3, giving [3,1,2,4]

Like magic it is.

Also, using the same technique, I rewrote the Array.each_permutation
method from Nano/Facets. This method runs about 25-30% slower, but it
uses O(N) memory instead of O(N!) memory, and wont fall over from a
stack overflow if you give it an array that's too long (though it will
eat your cpu until the end of eternity. Factorials over 10 get pretty
damn big).

class Array
    def each_permutation()
        perm_count = (1...size).inject(0) { |s,x| s + x * x.factorial }
        weights = Array.new(size-1) {|i| (i+1).factorial }
        s = weights.size
        x,i,v,pos = nil
        0.upto(perm_count) do |v|
            out = self[0..0]
            each_with_index {|x,i|
                case i
                    when 0: next
                    when s: out.insert(v / weights[i-1], x)
                    else out.insert(v % weights[i] / weights[i-1], x)
                end
            }        
            yield out
        end    
    end
end



#####################################################################################
This email has been scanned by MailMarshal, an email content filter.
#####################################################################################