Skip to content

Instantly share code, notes, and snippets.

@igorw

igorw/fannkuch.clj

Created January 10, 2015 00:17
Show Gist options
  • Save igorw/acf6f64a2e6199eda007 to your computer and use it in GitHub Desktop.
Save igorw/acf6f64a2e6199eda007 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. igorw created this gist Jan 10, 2015.
    79 changes: 79 additions & 0 deletions fannkuch.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,79 @@
    (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}