# Fun with Permutations

**URL:** <https://rubytalk.org/t/fun-with-permutations/22107>\
**Category:** ruby-talk\
**Created:** [3 November 2005 04:32 UTC](https://rubytalk.org/t/fun-with-permutations/22107 "2005-11-03T04:32:30Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Daniel\_Sheppard](https://avatars.discourse-cdn.com/v4/letter/d/db5fbb/32.png) [@Daniel\_Sheppard](https://rubytalk.org/u/Daniel_Sheppard)\
**Post date:** [3 November 2005 04:32 UTC](https://rubytalk.org/t/fun-with-permutations/22107/1 "2005-11-03T04:32:30Z")

</div>

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  
&nbsp;&nbsp;&nbsp;&nbsp;def permute(number)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;out = self[0..0]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nextfactor = factor = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;each\_with\_index {|x,i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when 0: next  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nextfactor = factor \* (i+1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;out.insert(number % nextfactor / factor, x)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;factor = nextfactor  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;out  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;def permutation\_number(original\_array=self.sort)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v = 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last\_indicies = Hash.new(0)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;original\_array.each\_with\_index {|x,i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next if i==0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m \*= i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;done = original\_array[0..i]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v += m \* self.select {|y| done.include?(y)}.rindex(x)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v  
&nbsp;&nbsp;&nbsp;&nbsp;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  
&nbsp;&nbsp;&nbsp;&nbsp;def each\_permutation()  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;perm\_count = (1...size).inject(0) { |s,x| s + x \* x.factorial }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;weights = Array.new(size-1) {|i| (i+1).factorial }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s = weights.size  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x,i,v,pos = nil  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0.upto(perm\_count) do |v|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;out = self[0..0]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;each\_with\_index {|x,i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when 0: next  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when s: out.insert(v / weights[i-1], x)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else out.insert(v % weights[i] / weights[i-1], x)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield out  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
end

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

---

<div class="post-metadata">

**Author:** ![Ammon\_Christiansen](https://avatars.discourse-cdn.com/v4/letter/a/7ba0ec/32.png) [@Ammon\_Christiansen](https://rubytalk.org/u/Ammon_Christiansen)\
**Post date:** [4 November 2005 00:34 UTC](https://rubytalk.org/t/fun-with-permutations/22107/2 "2005-11-04T00:34:37Z")

</div>

I was intrigued by your post. It looks really neat. And the memory/cpu time  
tradeoff is likely worth it.

I was doing a project called FindMaximumClique (a graph algorithm) which  
required me to enumerate and check all combinations (as opposed to your  
permutations) of subsets of vertices.

I found something on microsoft.com \<[http://microsoft.com](http://microsoft.com)\> that did the  
"next" combination. It wasn't as fancy as yours in that it couldn't do  
random access or tell you what order the array was sorted in, but you seem  
to want to do the permutations in order, so maybe there's an algorithm that  
allows you to do that in a simpler fashion using less CPU. The one I'm  
talking about was called lexicographical sort order on combinations (to  
uniquify the order of a sequence).

See

> **[Technical documentation](https://learn.microsoft.com/en-us/docs/)**

for a description  
or

> **[Microsoft Learn: Build skills that open doors in your career](https://learn.microsoft.com/en-us/)**
>
> Gain technical skills through documentation and training, earn certifications and connect with the community

for the code

It is in C#, and I ported it to Java.

Ammon

> **···**
>
> On 11/2/05, Daniel Sheppard \<daniels@pronto.com.au\> wrote:
> 
> > 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.
> > 
> > #####################################################################################

---

<div class="post-metadata">

**Author:** ![7rans](https://avatars.discourse-cdn.com/v4/letter/7/a8b319/32.png) [@7rans](https://rubytalk.org/u/7rans)\
**Post date:** [5 November 2005 17:07 UTC](https://rubytalk.org/t/fun-with-permutations/22107/3 "2005-11-05T17:07:11Z")

</div>

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

> **···**
>
> \<[malte.milatz@gmx.net](mailto:malte.milatz@gmx.net)\> wrote:
> 
> 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](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:
> 
> &nbsp;&nbsp;def factorial  
> &nbsp;&nbsp;&nbsp;&nbsp;return 0 if zero?  
> &nbsp;&nbsp;&nbsp;&nbsp;f = 1  
> &nbsp;&nbsp;&nbsp;&nbsp;2.upto(self) { |n| f \*= n }  
> &nbsp;&nbsp;&nbsp;&nbsp;f  
> &nbsp;&nbsp;end
> 
> That should help a good bit.
> 
> T.

---

<div class="post-metadata">

**Author:** ![Lyndon\_Samson](https://avatars.discourse-cdn.com/v4/letter/l/5f8ce5/32.png) [@Lyndon\_Samson](https://rubytalk.org/u/Lyndon_Samson)\
**Post date:** [6 November 2005 00:37 UTC](https://rubytalk.org/t/fun-with-permutations/22107/4 "2005-11-06T00:37:38Z")

</div>

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!

> **···**
>
> On 11/3/05, Daniel Sheppard \<daniels@pronto.com.au\> wrote:
> 
> > 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

---

<div class="post-metadata">

**Author:** ![Jay\_Anderson](https://avatars.discourse-cdn.com/v4/letter/j/ba9def/32.png) [@Jay\_Anderson](https://rubytalk.org/u/Jay_Anderson)\
**Post date:** [6 November 2005 22:42 UTC](https://rubytalk.org/t/fun-with-permutations/22107/5 "2005-11-06T22:42:11Z")

</div>

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  
&nbsp;&nbsp;&nbsp;&nbsp;def fact1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(1..self).inject { |n, fact| fact \* n }  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;def fact2  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(2..self).each { |n| fact \*= n }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;def fact3  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while i \<= self  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact \*= i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;def fact4  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2.upto(self) { |n| fact \*= n }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;def fact5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 0 if self \< 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 1 if self \< 2

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

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

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@\_n = 1

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

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

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

require 'benchmark'

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

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

[Benchmark.bm](http://Benchmark.bm)(20) do |bm|  
&nbsp;&nbsp;&nbsp;&nbsp;(1..7).each do |n|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bm.report("fact#{n}:") { TEST("fact#{n}") }  
&nbsp;&nbsp;&nbsp;&nbsp;end  
end

[Benchmark.bm](http://Benchmark.bm)(20) do |bm|  
&nbsp;&nbsp;&nbsp;&nbsp;(1..7).each do |n|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bm.report("fact#{n}:") { TESTBIG("fact#{n}") }  
&nbsp;&nbsp;&nbsp;&nbsp;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](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:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;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)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;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