1. Computer Language Shootout -- fannkuch
- Posted by Jason Gade <jaygade at gmail.com>
Jul 16, 2005
-
Last edited Jul 17, 2005
Okay, I'm stuck. This is one benchmark that has always stopped me.
On the fannkuch benchmark I don't understand the algorithm, especially
the "incremental change" algorithm for generating permutations. I've
studied the source code but I still don't get it.
Here is the description:
Each program should
* "Take a permutation of {1,...,n}, for example: {4,2,1,5,3}.
* Take the first element, here 4, and reverse the order of the
first 4 elements: {5,1,2,4,3}.
* Repeat this until the first element is a 1, so flipping won't
change anything more: {3,4,2,1,5}, {2,4,3,1,5}, {4,2,3,1,5}, {1,3,2,4,5}.
* Count the number of flips, here 5.
* Do this for all n! permutations, and record the maximum number of
flips needed for any permutation.
The conjecture is that this maximum count is approximated by n*log(n)
when n goes to infinity.
FANNKUCH is an abbreviation for the German word Pfannkuchen, or
pancakes, in analogy to flipping pancakes."
Each program should generate the same sequence of n! permutations - the
sequence generated by the incremental change algorithm implemented in
the C# and Oberon-2 programs.
http://shootout.alioth.debian.org/benchmark.php?test=fannkuch&lang=all&sort=fullcpu
Now I could probably just translate one or more of the programs to
Euphoria and trace it, but I would prefer to understand the algorithm
first. I could probably figure out the reversing part but I don't
understand how to find every permutation using the incremental change
method. Does anyone else understand how it works and can explain it in
plain english or pseudo code?
So far I've found the FORTRAN source the most clear which is strange in
itself.
--
==============================
Too many freaks, not enough circuses.
j.
