Fun with Permutations

[Daniel Sheppard]

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 =20
=20 def permute(number)
=20 out =3D self[0..0]
=20 nextfactor =3D factor =3D 1
=20 each_with_index {|x,i|
=20 case i
=20 when 0: next
=20 else=20
=20 nextfactor =3D factor * (i+1)
=20 out.insert(number % nextfactor / factor, x)
=20 factor =3D nextfactor
=20 end
=20 } =20
=20 out
=20 end
=20 def permutation_number(original_array=3Dself.sort)
=20 m =3D 1
=20 v =3D 0
=20 last_indicies =3D Hash.new(0)
=20 original_array.each_with_index {|x,i|
=20 next if i=3D=3D0
=20 m *=3D i
=20 done =3D original_array[0..i]
=20 v +=3D m * self.select {|y| done.include?(y)}.rindex(x)
=20 }
=20 v
=20 end
end

[3,1,2,4].permutation_number
=3D> 19
[1,2,3,4].permute(19)
=3D> [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! =3D 18, leaves 1
0 * 2! =3D 0, leaves 1
1 * 1! =3D 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
=20 def each_permutation()
=20 perm_count =3D (1...size).inject(0) { |s,x| s + x * x.factorial=
=20}
=20 weights =3D Array.new(size-1) {|i| (i+1).factorial }
=20 s =3D weights.size
=20 x,i,v,pos =3D nil
=20 0.upto(perm_count) do |v|
=20 out =3D self[0..0]
=20 each_with_index {|x,i|
=20 case i
=20 when 0: next
=20 when s: out.insert(v / weights[i-1], x)
=20 else out.insert(v % weights / weights[i-1], x)
=20 end
=20 } =20
=20 yield out
=20 end =20
=20 end
end



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

 

[Trans]

Sorry it took me some time to get to this. I've been quite busy. This
is very interesting and I'll see that it gets into Facets. I think the
trade off is worth it too. But even better I think it can be improved.

I recently got an interesting email (that I've also been meaning to get
to) on the efficency of factorial algorithms, Malte Milatz

On a German Ruby board, we've been discussing about the best way to
compute the factorial of a number. While I don't suppose you to
understand German, it would be nice if you had a look at the code and
the benchmarks at <http://www.rubyforen.de/ptopic,6946.html>.

The result of our research seems to be that using inject is a highly
inefficient way in this case because the block for Enumerable#inject
takes two arguments. This may be a good reason to revise the method
found in 'facet/integer/fact'.

Note that we discarded the nil assignments seen in the first post, for
they didn't really improve things. In addition murphy changed the
benchmark to compute only up to 12! because tests on higher factorials
will be likely to be only tests on Bignum arithmetics.

;;

So in your formuation I see an inject with factorial in it. Perhaps a
little coding challenge to speed it up. And I've just added the new
factorial code to facets:

def factorial
return 0 if zero?
f = 1
2.upto(self) { |n| f *= n }
f
end

That should help a good bit.

T.

 

[Lyndon Samson]

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

Cool. Although maybe call them unsort

Knuth has a fascile out of TAOCP Vol 4 called Generating All Tuples
and Permutations. You may find worth a look. There is some interesting
stuff in there about the relationship between permutations and English
bell ringers!

 

[horndude77]

Sorry if this doesn't totally apply to this thread, but I felt like
playing with the factorial function for a bit. After taking a look at
the german thread I decided to see if I could speed it up also. Here's
what I came up with:

class Integer
def fact1
(1..self).inject { |n, fact| fact * n }
end
def fact2
fact = 1
(2..self).each { |n| fact *= n }
fact
end
def fact3
fact = 1
i = 1
while i <= self
fact *= i
i += 1
end
fact
end
def fact4
fact = 1
2.upto(self) { |n| fact *= n }
fact
end
def fact5
return 0 if self < 1
return 1 if self < 2

prod = 1
n = self
step = 10
mul = 2
if(self%2 == 1) then
prod = self
n -= 1
end

while(n>0)
prod *= mul
mul += step
step += 8
n -= 2
end
prod
end
def fact6
return 0 if self<0
return 1 if self<2
return 2 if self==2
endnum = self
fact = 1
if self % 3 == 1 then
fact = self
endnum = self - 1
elsif self % 3 == 2 then
fact = self*(self-1)
endnum = self - 2
end
n = 1
while n<self
fact *= n*(n+1)*(n+2)
n += 3
end
fact
end
def fact7
return 1 if self < 2

p = 1
r = 1
@_n = 1

log2n = (Math.log(self)/Math.log(2)).floor
h = 0
shift = 0
high = 1
len = 0

while(h != self)
shift += h;
h = self >> log2n;
log2n -= 1
len = high
high = (h & 1) == 1 ? h : h - 1
len = (high - len) / 2

if(len > 0) then
p *= product(len)
r *= p
end
end
return r << shift;
end
def product(n)
m = n/2
if(m == 0) then
@_n += 2
return @_n
end
if(n == 2)
@_n += 4
return @_n*(@_n-2)
end
product(n-m)*product(m)
end
end

require 'benchmark'

def TESTBIG(meth)
3.times { (10..600).each { |i| i.send meth } }
end

def TEST(meth)
1000.times do
for i in 0..12
i.send meth
end
end
end

Benchmark.bm(20) do |bm|
(1..7).each do |n|
bm.report("fact#{n}:") { TEST("fact#{n}") }
end
end

Benchmark.bm(20) do |bm|
(1..7).each do |n|
bm.report("fact#{n}:") { TESTBIG("fact#{n}") }
end
end


I added the last three functions.

'fact5' uses this pattern to optimize the algorithm:
1*2 = 2
3*4 = 12 - 2 = 10
5*6 = 30 - 12 = 18 - 10 = 8
7*8 = 56 - 30 = 26 - 18 = 8
9*10 = 90 - 56 = 34 - 26 = 8
11*12 = 132 - 90 = 42 - 34 = 8
So it replaces a multiplication with a few additions. (not enough space
to fully explain it here)

'fact6' just unrolls the loop a bit.

'fact7' I got from
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm and I
have no idea how it really works since there is no explaination on the
page. I just converted the code to ruby. I haven't sat down yet to
figure out how it works.

Here are my results:
user system total real
fact1: 0.260000 0.040000 0.300000 ( 0.318653)
fact2: 0.160000 0.030000 0.190000 ( 0.187645)
fact3: 0.090000 0.010000 0.100000 ( 0.106474)
fact4: 0.120000 0.030000 0.150000 ( 0.154318)
fact5: 0.090000 0.010000 0.100000 ( 0.108911)
fact6: 0.110000 0.000000 0.110000 ( 0.116655)
fact7: 0.250000 0.020000 0.270000 ( 0.283975)
user system total real
fact1: 3.540000 0.420000 3.960000 ( 3.964279)
fact2: 2.180000 0.210000 2.390000 ( 2.399197)
fact3: 1.960000 0.000000 1.960000 ( 1.968284)
fact4: 2.190000 0.190000 2.380000 ( 2.383942)
fact5: 1.120000 0.000000 1.120000 ( 1.133676)
fact6: 0.820000 0.000000 0.820000 ( 0.821641)
fact7: 1.050000 0.080000 1.130000 ( 1.129524)

It is somewhat annoying that unrolling the loop works that well for
larger numbers, but whatever works I guess. The other two also seem to
work fairly well.

The next thing to try would be the other fast algorithms from that fast
factorial page.

Ok, well hopefully this will be interesting to some.

-----Horndude77