From: Daniel Sheppard <daniels@...>
Date: 2005-11-07T09:20:45+09:00
Subject: Re: Fun with Permutations (including new change for Facets)

Eeep. Seems I never actually sent this email... I hate it when I do
that....

It bugged me that my fancy new algorithym wasn't faster than the old
one, so I MADE it faster, goddammit. This beats out the
facets/array/each_permutation by 6-60%, depending on array size. The
second method seems to run slightly faster than the first, but they're
really much of a muchness, and the first is a lot more readable. I think
I was wrong about the difference in memory usage between my solutions
and facets - I don't think memory usage is an advantage here. I think
the advantage here is that this method is not recursive, so it's not
prone to stack overflows, and (now) it's faster.

This is my favourite - it's fastest, and displays the permutations in
the 'correct' order (ie, the first permutation of the first permutation
is equal to the second permutation of the original).

    def each_permutation_new3()
        pos = Array.new(size) {|i| i}
        s = (0...size).to_a.reverse
        out = nil
        while true
            out = []
            pos.each_with_index {|p,i| out.insert(p, self[i]) }
            yield out
            break if s.each { |i|
                break if pos[i] > 0 && pos[i] -= 1
                pos[i] = i
            }
        end 
    end

Benchmarks against the old method for doing permutations on arrays up to
size 9:

                        user     system      total        real
old  2x100000:      4.328000   0.016000   4.344000 (  4.438000)
new3 2x100000:      4.172000   0.031000   4.203000 (  4.234000)
--
old  3x10000:       1.765000   0.000000   1.765000 (  1.828000)
new3 3x10000:       1.172000   0.000000   1.172000 (  1.219000)
--
old  4x2000:        1.610000   0.016000   1.626000 (  1.641000)
new3 4x2000:        1.062000   0.000000   1.062000 (  1.062000)
--
old  5x1000:        4.328000   0.031000   4.359000 (  4.438000)
new3 5x1000:        2.985000   0.016000   3.001000 (  3.078000)
--
old  6x200:         5.406000   0.046000   5.452000 (  5.687000)
new3 6x200:         4.187000   0.032000   4.219000 (  4.297000)
--
old  7x50:         10.016000   0.109000  10.125000 ( 10.422000)
new3 7x50:          8.125000   0.031000   8.156000 (  8.375000)
--
old  8x20:         32.812000   0.063000  32.875000 ( 33.344000)
new3 8x20:         29.016000   0.203000  29.219000 ( 29.766000)
--
old  9x2:          30.594000   0.172000  30.766000 ( 31.375000)
new3 9x2:          28.844000   0.140000  28.984000 ( 29.406000)

(Benchmarks for higher array sizes are left as an exercise for the
reader's supercomputer).


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