--            Haskell programs for A210585 and some other
--                 sequences concerning Lyndon words
--            -------------------------------------------

import OEISaux (bFile, oeisTrim)
import Data.List (isPrefixOf)
import Data.Set (Set, fromList, insert, deleteFindMin)

newtype Wrd = Wrd [Int] deriving (Eq)
instance Ord Wrd where
   Wrd xs <= Wrd ys | length xs == length ys = xs <= ys
                    | otherwise              = length xs <= length ys

lyndonWordsOn k
   | k > 9     = error "+++ decimal alphabet only +++"
   | otherwise = g [] $ fromList $ map (Wrd . (: [])) [1..k] where

   g :: [[Int]] -> Set Wrd -> [Integer]
   g powers s
     | isLyndon wrd = foldl (\v d -> 10 * v + toInteger d) 0 wrd
                      : g ((cycle wrd) : powers) s''
     | otherwise    = g powers s''
     where (Wrd wrd, s') = deleteFindMin s

           s'' = foldl (flip insert) s' (map (Wrd . (: wrd)) [1..k])

           isLyndon :: [Int] -> Bool
           isLyndon zs = early (tail zs ++ init zs) &&
                         (not $ or $ map (zs `isPrefixOf`) powers)
             where early :: [Int] -> Bool
                   early xs = length zs > length xs ||
                              zs < xs && early (tail xs)

-- ---------------------------------------------------------------------

-- A102659 List of Lyndon words on {1,2}
--         sorted first by length and then lexicographically.
a102659 n = a102659_list !! (n-1)
a102659_list = lyndonWordsOn 2
b102659 = bFile "A102659" a102659_list 1 10000

-- A102660 List of Lyndon words on {1,2,3}
--         sorted first by length and then lexicographically.
a102660 n = a102660_list !! (n-1)
a102660_list = lyndonWordsOn 3
b102660 = bFile "A102660" a102660_list 1 10000

-- A210584 List of Lyndon words on {1,2,3,4}
--         sorted first by length and then lexicographically.
a210584 n = a210584_list !! (n-1)
a210584_list = lyndonWordsOn 4
b210584 = bFile "A210584" a210584_list 1 10000

-- A210585 List of Lyndon words on {1,...,8}
--         sorted first by length and then lexicographically.
a210585 n = a210585_list !! (n-1)
a210585_list = lyndonWordsOn 8
b210585 = bFile "A210585" a210585_list 1 10000

-- ---------------------------------------------------------------------
--                                       Reinhard Zumkeller, Mar 23 2012
--                                          reinhard.zumkeller@gmail.com