Skip to content

Instantly share code, notes, and snippets.

@blackdrag
Created January 9, 2015 10:37
Show Gist options
  • Save blackdrag/2fe23cf13a0f013c48a1 to your computer and use it in GitHub Desktop.
Save blackdrag/2fe23cf13a0f013c48a1 to your computer and use it in GitHub Desktop.
def min=100000,max=0, sum=0
def iterations = 10
iterations.times {
def n = 10
long t1 = System.nanoTime()
def r = fannkuch(n)
long t2 = System.nanoTime()
//println("Pfannkuchen(" + n + ") = " + r)
def t = (t2 - t1) / 1_000_000
println "time = " + t
if (t<min) min=t
if (t>max) max=t
sum+=t
}
println "time avg. ${sum/iterations} ms, -${(sum/iterations)-min},/+${max-sum/iterations}"
@CompileStatic
def fannkuch(int n) {
int check = 0
int[] perm = new int[n]
int[] perm1 = new int[n]
int[] count = new int[n]
int[] maxPerm = new int[n]
int maxFlipsCount = 0
int m = n - 1
for (int i=0;i<n;i++) {
perm1[i] = i
}
int r = n
while (true) {
// write-out the first 30 permutations
while (r != 1) {
count[r - 1] = r
r--
}
if (!(perm1[0] == 0 || perm1[m] == m)) {
for (int i=0; i<n; i++) {
perm[i] = perm1[i]
}
int flipsCount = 0
int k
while (!((k = perm[0]) == 0)) {
int k2 = (k + 1) >> 1
for (int i=0; i<k2; i++) {
int temp = perm[i]
perm[i] = perm[k - i]
perm[k - i] = temp
}
flipsCount++
}
if (flipsCount > maxFlipsCount) {
maxFlipsCount = flipsCount
for (int i=0; i<n; i++) {
maxPerm[i] = perm1[i]
}
}
}
while (true) {
if (r == n) {
return maxFlipsCount
}
int perm0 = perm1[0]
int i = 0
while (i < r) {
int j = i + 1
perm1[i] = perm1[j]
i = j
}
perm1[r] = perm0
count[r] = count[r] - 1
if (count[r] > 0) {
break
}
r++
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment