Skip to content

Instantly share code, notes, and snippets.

@7shi 7shi/ClifEven.fsx
Last active Jan 16, 2020

Embed
What would you like to do?
[F#] Clifford even subalgebra
let memoize (f: 'k -> 'v) =
let cache = System.Collections.Generic.Dictionary<'k, 'v>()
fun a ->
let b, v = cache.TryGetValue a
if b then v else
let ret = f a
cache.[a] <- ret
ret
let curry f = fun a b -> f(a, b)
let uncurry f = fun(a, b) -> f a b
let combination =
let rec f n = function
| k when k < 1 -> []
| 1 -> [ for i in 1..n -> [i] ]
| k -> [ for c in g (n - 1) (k - 1) do
for i in (List.max c) + 1 .. n -> List.append c [i] ]
and g = f |> uncurry |> memoize |> curry
g
let clifford = memoize <| fun n ->
[for i in 1..n do yield! combination n i]
let clifcont p xs =
let rec f n a = function
| [] -> n, a
| xs ->
let m = List.min xs
let ys = Seq.zip (Seq.initInfinite id) xs
|> Seq.filter (snd >> (=) m)
|> Seq.map fst
|> Seq.toArray
let l = ys.Length
let xchg = (Array.sum ys) - ((l - 1) * l) / 2 // 0121 -> 1, 1021 -> 2, 1102
let cntr = if m <= p then 0 else l / 2
f (n + xchg + cntr) (if l % 2 = 0 then a else m::a) (List.filter ((<>) m) xs)
let n, xs = f 0 [] xs
(if n % 2 = 0 then 1 else -1), xs |> List.rev
let clifnorm p xs =
clifcont p (List.append xs xs) |> fst
let clifxchg p a b =
clifcont p (List.append a b) = clifcont p (List.append b a)
let clifpm cl =
let p, m =
cl |> Seq.filter (fst >> (=) 1) |> Seq.map snd,
cl |> Seq.filter (fst >> (=) -1) |> Seq.map snd
Seq.length p, Seq.append p m |> Seq.toArray
let clifiso p bs =
let p2, bs = bs |> Seq.map (fun b -> clifnorm p b, b) |> clifpm
let ng =
seq {
for cl in clifford (Seq.length bs) do
let n1 = clifnorm p2 cl
let n2 = [for b in cl do yield! bs.[b - 1]] |> clifnorm p
if n1 <> n2 then yield () }
seq { if Seq.isEmpty ng then yield p2 }
let clif2 n p =
let clif = clifford (n - 1)
let f m =
seq { for i in 1..n do
if i <> m then yield [m; i] }
|> clifiso p
seq { if p > 0 then yield! f 1
if p < n then yield! f n }
|> Seq.distinct
|> Seq.toList
seq { for i in 0..7 -> i.ToString() } |> String.concat "|" |> printfn "p\m|%s"
seq { for i in -1..7 -> "----" } |> String.concat "|" |> printfn "%s"
for i = 0 to 7 do
printf "%d" i
for j = 0 to 7 do
printf "|"
if i + j < 2 then () else
clif2 (i + j) i
|> List.map (fun n -> sprintf @"(%d,%d)" n (i + j - n - 1))
|> String.concat ","
|> printf "%s"
printfn ""
p\m 0 1 2 3 4 5 6 7
0 (0,1) (0,2) (0,3) (0,4) (0,5) (0,6)
1 (1,0) (2,0),(1,1) (3,0),(1,2) (4,0),(1,3) (5,0),(1,4) (6,0),(1,5) (7,0),(1,6)
2 (0,1) (1,1),(2,0) (2,1) (3,1),(2,2) (4,1),(2,3) (5,1),(2,4) (6,1),(2,5) (7,1),(2,6)
3 (0,2) (1,2),(3,0) (2,2),(3,1) (3,2) (4,2),(3,3) (5,2),(3,4) (6,2),(3,5) (7,2),(3,6)
4 (0,3) (1,3),(4,0) (2,3),(4,1) (3,3),(4,2) (4,3) (5,3),(4,4) (6,3),(4,5) (7,3),(4,6)
5 (0,4) (1,4),(5,0) (2,4),(5,1) (3,4),(5,2) (4,4),(5,3) (5,4) (6,4),(5,5) (7,4),(5,6)
6 (0,5) (1,5),(6,0) (2,5),(6,1) (3,5),(6,2) (4,5),(6,3) (5,5),(6,4) (6,5) (7,5),(6,6)
7 (0,6) (1,6),(7,0) (2,6),(7,1) (3,6),(7,2) (4,6),(7,3) (5,6),(7,4) (6,6),(7,5) (7,6)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.