OpenEuphoria

Computer Language Shootout -- fannkuch

• Posted by Jason Gade <jaygade at gmail.com> Jul 16, 2005
• 509 views

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.