Created
July 5, 2012 07:47
-
-
Save gozzoo/3052132 to your computer and use it in GitHub Desktop.
annkuchredux benchmark implementation in javascript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function fannkuchredux(n) { | |
var perm = new Array(n); | |
var perm1 = new Array(n); | |
var count = new Array(n); | |
var maxFlipsCount = 0; | |
var permCount = 0; | |
var checksum = 0; | |
var i; | |
for (i = 0; i < n; i++) | |
perm1[i] = i; | |
var r = n; | |
while (true) { | |
while (r != 1) { | |
count[r-1] = r; | |
r -= 1; | |
} | |
for (i = 0; i < n; i += 1) | |
perm[i] = perm1[i]; | |
var flipsCount = 0; | |
for (var k = perm[0]; k != 0; k = perm[0]) { | |
var k2 = (k+1) >> 1; | |
for (i = 0; i < k2; i++) { | |
var temp = perm[i]; | |
perm[i] = perm[k-i]; | |
perm[k-i] = temp; | |
} | |
flipsCount += 1; | |
} | |
if (flipsCount > maxFlipsCount) | |
maxFlipsCount = flipsCount; | |
var csi = flipsCount; | |
if (permCount % 2 != 0) | |
csi = -flipsCount; | |
checksum += csi; | |
while (true) { | |
if (r == n) { | |
console.log(checksum); | |
return maxFlipsCount; | |
} | |
var perm0 = perm1[0]; | |
i = 0; | |
while (i < r) { | |
var j = i + 1; | |
perm1[i] = perm1[j]; | |
i = j; | |
} | |
perm1[r] = perm0; | |
count[r] = count[r] - 1; | |
if (count[r] > 0) | |
break; | |
r++; | |
} | |
permCount++; | |
} | |
//return 0; | |
} | |
var n = 11; | |
var res = fannkuchredux(n); | |
console.log("Pfannkuchen(" + n + ") = " + res); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment