fannkuch.clj

(ns fannkuch.core
  (:require [clojure.math.combinatorics :as combo]))

; Fannkuchen
;
; it's super slow though
; also I was too stupid to implement permutations, so I used Mark Engelberg's library
;
; https://www.haskell.org/haskellwiki/Shootout/Fannkuch

(defn permutations
  [n]
  (combo/permutations (range 1 (inc n))))

(defn flip
  [xs]
  (let [n (first xs)
        [first-n rest] (split-at n xs)]
    (concat (reverse first-n) rest)))

(defn flips
  [xs]
  (let [iterations (iterate flip xs)
        [a b] (split-with #(not (= (first %) 1)) iterations)]
    (concat a (take 1 b))))

(defn max-flips-of-permutations
  [n]
  (let [perms (permutations n)]
    {:perms (take 30 perms)
     :max-count (apply max (map #(dec (count (flips %))) perms))}))

; (use 'fannkuch.core :reload)

; (permutations 3)
;=> ([1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1])

; (flip [3 1 2])
;=> (2 1 3)
; (flip *1)
;=> (1 2 3)
; (flip *1)
;=> (1 2 3)

; (flips [3 1 2])
;=> ([3 1 2] (2 1 3) (1 2 3))

; (max-flips-of-permutations 7)
;=> {:perms ([1 2 3 4 5 6 7]
;            [1 2 3 4 5 7 6]
;            [1 2 3 4 6 5 7]
;            [1 2 3 4 6 7 5]
;            [1 2 3 4 7 5 6]
;            [1 2 3 4 7 6 5]
;            [1 2 3 5 4 6 7]
;            [1 2 3 5 4 7 6]
;            [1 2 3 5 6 4 7]
;            [1 2 3 5 6 7 4]
;            [1 2 3 5 7 4 6]
;            [1 2 3 5 7 6 4]
;            [1 2 3 6 4 5 7]
;            [1 2 3 6 4 7 5]
;            [1 2 3 6 5 4 7]
;            [1 2 3 6 5 7 4]
;            [1 2 3 6 7 4 5]
;            [1 2 3 6 7 5 4]
;            [1 2 3 7 4 5 6]
;            [1 2 3 7 4 6 5]
;            [1 2 3 7 5 4 6]
;            [1 2 3 7 5 6 4]
;            [1 2 3 7 6 4 5]
;            [1 2 3 7 6 5 4]
;            [1 2 4 3 5 6 7]
;            [1 2 4 3 5 7 6]
;            [1 2 4 3 6 5 7]
;            [1 2 4 3 6 7 5]
;            [1 2 4 3 7 5 6]
;            [1 2 4 3 7 6 5]),
;    :max-count 16}