diff options
Diffstat (limited to '')
-rw-r--r-- | dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch.go | 125 |
1 files changed, 125 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch.go b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch.go new file mode 100644 index 0000000..4f07dff --- /dev/null +++ b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch.go @@ -0,0 +1,125 @@ +//go:build ignore +// +build ignore + +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * Based on fannkuch.c by Heiner Marxen + */ + +package main + +import ( + "flag" + "fmt" +) + +var n = flag.Int("n", 7, "count") + +func fannkuch(n int) int { + if n < 1 { + return 0 + } + + n1 := n - 1 + perm := make([]int, n) + perm1 := make([]int, n) + count := make([]int, n) + + for i := 0; i < n; i++ { + perm1[i] = i // initial (trivial) permutation + } + + r := n + didpr := 0 + flipsMax := 0 + for { + if didpr < 30 { + for i := 0; i < n; i++ { + fmt.Printf("%d", 1+perm1[i]) + } + fmt.Printf("\n") + didpr++ + } + for ; r != 1; r-- { + count[r-1] = r + } + + if perm1[0] != 0 && perm1[n1] != n1 { + flips := 0 + for i := 1; i < n; i++ { // perm = perm1 + perm[i] = perm1[i] + } + k := perm1[0] // cache perm[0] in k + for { // k!=0 ==> k>0 + for i, j := 1, k-1; i < j; i, j = i+1, j-1 { + perm[i], perm[j] = perm[j], perm[i] + } + flips++ + // Now exchange k (caching perm[0]) and perm[k]... with care! + j := perm[k] + perm[k] = k + k = j + if k == 0 { + break + } + } + if flipsMax < flips { + flipsMax = flips + } + } + + for ; r < n; r++ { + // rotate down perm[0..r] by one + perm0 := perm1[0] + for i := 0; i < r; i++ { + perm1[i] = perm1[i+1] + } + perm1[r] = perm0 + count[r]-- + if count[r] > 0 { + break + } + } + if r == n { + return flipsMax + } + } + return 0 +} + +func main() { + flag.Parse() + fmt.Printf("Pfannkuchen(%d) = %d\n", *n, fannkuch(*n)) +} |