Class.hs

-- |
-- Module      : Math.Sym.Class
-- Copyright   : (c) Anders Claesson 2012, 2013
-- 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
    (
      inc, dec
    , av123, av132, av213, av231, av312, av321
    , vee, caret, gt, lt, wedges, separables
    ) where

import Math.Sym (Perm, empty, one, idperm, (/+/), (\-\), ssum, normalize)
import Math.Sym.Bijection (simionSchmidt')
import qualified Math.Sym.D8 as D8

-- | The class of increasing permutations.
inc :: Perm a => Int -> [a]
inc n = [idperm n]

-- | The class of decreasing permutations.
dec :: Perm a => Int -> [a]
dec n = [D8.complement (idperm n)]

-- | Av(123).
av123 :: Perm a => Int -> [a]
av123 = map simionSchmidt' . av132

-- | Av(132).
av132 :: Perm a => Int -> [a]
av132 = map D8.reverse . av231

-- | Av(213).
av213 :: Perm a => Int -> [a]
av213 = map D8.complement . av231

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

streamAv231 :: Perm a => [[a]]
streamAv231 = map av231 [0..]

-- | Av(312).
av312 :: Perm a => Int -> [a]
av312 = map D8.reverse . av213

-- | Av(321).
av321 :: Perm a => Int -> [a]
av321 = map D8.complement . av123

-- | 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 :: Perm a => Int -> [a]
vee = (streamVee !!)

streamVee :: Perm a => [[a]]
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 ∧.
caret :: Perm a => Int -> [a]
caret = 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 :: Perm a => Int -> [a]
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 :: Perm a => Int -> [a]
lt = map D8.reverse . gt

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

-- | The union of 'vee', 'caret', 'gt' and 'lt'.
wedges :: Perm a => Int -> [a]
wedges = union [vee, caret, gt, lt]

compositions :: Int -> Int -> [[Int]]
compositions 0 0 = [[]]
compositions 0 _ = []
compositions _ 0 = []
compositions k n = [1..n] >>= \i -> map (i:) (compositions (k-1) (n-i))

-- | The class of separable permutations; it is identical to Av(2413,3142).
separables :: Perm a => Int -> [a]
separables 0 = [empty]
separables 1 = [ one ]
separables n = pIndec n ++ mIndec n
    where
      comps  m = [2..m] >>= \k -> compositions k m
      pIndec 0 = []
      pIndec 1 = [one]
      pIndec m = comps m >>= map ssum . mapM (streamMIndec !!)
      mIndec m = map D8.complement $ pIndec m
      streamMIndec = map mIndec [0..]