Anonymous user
De Bruijn sequences: Difference between revisions
→{{header|Haskell}}: added alternative solution
(→{{header|Haskell}}: added solution) |
(→{{header|Haskell}}: added alternative solution) |
||
Line 1,321:
=={{header|Haskell}}==
=== Permutation-based ===
Straight-forward implementation of inverse Burrows—Wheeler transform [https://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction] is reasonably efficient for the task (about a milliseconds for B(10,4) in GHCi).
Line 1,340:
-- the set of Lyndon words generated by inverse Burrows—Wheeler transform
lyndonWords :: Ord a =>
lyndonWords
where
ref = concat $ replicate (length s ^ (
perm = s >>= (`elemIndices` ref)
-- returns the de Bruijn sequence of order
deBruijn :: Ord a =>
deBruijn
in lw ++ take (
<pre>λ> cycleForm [1,4,3,2,0]
[[1,4,0],[3,2]]
λ> lyndonWords
["a","aab","abb","b"]
λ> deBruijn
"aaababbbaa"</pre>
Line 1,366:
main = do
let symbols = ['0'..'9']
let db = deBruijn
putStrLn $ "The length of de Bruijn sequence: " ++ show (length db)
putStrLn $ "The first 130 symbols are:\n" ++ show (take 130 db)
Line 1,386:
Words not in the sequence:
Words not in the corrupted sequence: 1459 4591 5914 8145</pre>
=== Array-based ===
{{trans|Python}}
<lang haskell>import Control.Monad.State
import Data.Array ((!), (//))
import qualified Data.Array as A
deBruijn :: [a] -> Int -> [a]
deBruijn s n =
let
k = length s
db t p =
if t > n
then
if n `mod` p == 0
then get >>= \a -> return [ a ! k | k <- [1 .. p]]
else return []
else do
a <- get
x <- setArray t (a ! (t-p)) >> db (t+1) p
a <- get
y <- sequence [ setArray t j >> db (t+1) t
| j <- [a ! (t-p) + 1 .. k - 1] ]
return $ x ++ concat y
setArray i x = modify (// [(i, x)])
seqn = db 1 1 `evalState` A.listArray (0, k*n-1) (repeat 0)
in [ s !! i | i <- seqn ++ take (n-1) seqn ]</lang>
=={{header|J}}==
| |||