-- |
-- Module      : Math.Sym.Class
-- Copyright   : (c) Anders Claesson 2012
-- License     : BSD-style
-- Maintainer  : Anders Claesson <anders.claesson@gmail.com>
-- 
-- A permutation class is a downset in the poset of permutations
-- ordered by containment. This module provides definitions of some
-- common classes.

module Math.Sym.Class
    (
     av231, vee, wedge, gt, lt, vorb
    ) where

import Data.Monoid ((<>))
import Math.Sym (empty, one, (/-/), StPerm, normalize)
import Math.Sym.D8 as D8

-- | Av(231); also know as the stack sortable permutations.
av231 :: Int -> [StPerm]
av231 0 = [empty]
av231 n = do
  k <- [0..n-1]
  s <- streamAv231 !! k
  t <- streamAv231 !! (n-k-1)
  return $ s <> (one /-/ t)

streamAv231 :: [[StPerm]]
streamAv231 = map av231 [0..]

-- | The V-class is Av(132, 231). It is so named because the diagram
-- of a typical permutation in this class is shaped like a V.
vee :: Int -> [StPerm]
vee = (streamVee !!)

streamVee :: [[StPerm]]
streamVee = [empty] : [one] : zipWith (++) vee_n n_vee
    where
      n_vee = (map.map) (one /-/) ws
      vee_n = (map.map) ( <> one) ws
      ws    = tail streamVee

-- | The ∧-class is Av(213, 312). It is so named because the diagram
-- of a typical permutation in this class is shaped like a wedge.
wedge :: Int -> [StPerm]
wedge = map D8.complement . vee

-- | The >-class is Av(132, 312). It is so named because the diagram
-- of a typical permutation in this class is shaped like a >.
gt :: Int -> [StPerm]
gt = map D8.rotate . vee

-- | The <-class is Av(213, 231). It is so named because the diagram
-- of a typical permutation in this class is shaped like a <.
lt :: Int -> [StPerm]
lt = map D8.reverse . gt

union :: [Int -> [StPerm]] -> Int -> [StPerm]
union cs n = normalize $ concat [ c n | c <- cs ]

-- | The union of 'vee', 'wedge', 'gt' and 'lt'; the orbit of a V under rotation
vorb :: Int -> [StPerm]
vorb = union [vee, wedge, gt, lt]