| -- The Computer Language Shootout |
| -- http://shootout.alioth.debian.org/ |
| -- contributed by Mike Pall |
| |
| local function fannkuch(n) |
| local p, q, s, odd, check, maxflips = {}, {}, {}, true, 0, 0 |
| for i=1,n do p[i] = i; s[i] = i end |
| repeat |
| -- Print max. 30 permutations. |
| if check < 30 then |
| if not p[n] then return maxflips end -- Catch n = 0, 1, 2. |
| for i=1,n do io.write(p[i]) end; io.write("\n") |
| check = check + 1 |
| end |
| -- Copy and flip. |
| local q1 = p[1] -- Cache 1st element. |
| if p[n] ~= n and q1 ~= 1 then -- Avoid useless work. |
| for i=2,n do q[i] = p[i] end -- Work on a copy. |
| for flips=1,1000000 do -- Flip ... |
| local j = q1 - 1 |
| for i=2,q1/2 do q[i], q[j] = q[j], q[i]; j = j - 1 end |
| local qq = q[q1] |
| if qq == 1 then -- ... until 1st element is 1. |
| if flips > maxflips then maxflips = flips end -- New maximum? |
| break |
| end |
| q[q1] = q1 |
| q1 = qq |
| end |
| end |
| -- Permute. |
| if odd then |
| p[2], p[1] = p[1], p[2]; odd = false -- Rotate 1<-2. |
| else |
| p[2], p[3] = p[3], p[2]; odd = true -- Rotate 1<-2 and 1<-2<-3. |
| for i=3,n do |
| local sx = s[i] |
| if sx ~= 1 then sx = sx - 1; s[i] = sx; break end |
| if i == n then return maxflips end -- Out of permutations. |
| s[i] = i |
| -- Rotate 1<-...<-i+1. |
| local t = p[1]; for j=1,i do p[j] = p[j+1] end; p[i+1] = t |
| end |
| end |
| until false |
| end |
| |
| local n = tonumber(arg and arg[1]) or 1 |
| io.write("Pfannkuchen(", n, ") = ", fannkuch(n), "\n") |