Anonymous user
Latin Squares in reduced form: Difference between revisions
→{{header|Haskell}}: added solution
m (Fixed typo.) |
(→{{header|Haskell}}: added solution) |
||
Line 766:
Order 6: Size 9408 x 6! x 5! => Total 812851200
</pre>
=={{header|Haskell}}==
The solution uses permutation generator given by '''Data.List''' package and List monad for generating all possible latin squares as a fold of permutation list.
<lang haskell>import Data.List (permutations, (\\))
import Control.Monad (foldM, forM_)
import Text.Printf
latinSquares :: Eq a => [a] -> [[[a]]]
latinSquares [] = []
latinSquares set = map reverse <$> squares
where
squares = foldM addRow firstRow perm
perm = tail (groupedPermutations set)
firstRow = pure <$> set
addRow tbl rows = [ zipWith (:) row tbl
| row <- rows
, and $ different (tail row) (tail tbl) ]
different = zipWith $ (not .) . elem
groupedPermutations :: Eq a => [a] -> [[[a]]]
groupedPermutations lst = map (\x -> (x :) <$> permutations (lst \\ [x])) lst
printTable :: Show a => [[a]] -> IO ()
printTable tbl = putStrLn $ unlines $ unwords . map show <$> tbl
</lang>
It is slightly optimized by grouping permutations by the first element according to a set order. Partitioning reduces the filtering procedure by factor of an initial set size.
'''Examples'''
<pre>λ> latinSquares "abc"
[["abc","bca","cab"]]
λ> mapM_ printTable $ take 3 $ latinSquares [1..9]
1 2 3 4 5 6 7 8 9
2 9 4 8 1 7 3 6 5
3 8 2 5 9 1 4 7 6
4 7 5 6 2 9 8 1 3
5 6 9 1 3 8 2 4 7
6 5 1 7 4 2 9 3 8
7 4 6 3 8 5 1 9 2
8 3 7 9 6 4 5 2 1
9 1 8 2 7 3 6 5 4
1 2 3 4 5 6 7 8 9
2 9 4 8 1 7 3 5 6
3 8 2 5 9 1 4 6 7
4 7 5 6 2 9 8 1 3
5 6 9 1 3 8 2 7 4
6 5 1 7 4 2 9 3 8
7 4 6 3 8 5 1 9 2
8 3 7 9 6 4 5 2 1
9 1 8 2 7 3 6 4 5
1 2 3 4 5 6 7 8 9
2 9 4 8 1 7 3 6 5
3 8 2 5 9 1 4 7 6
4 7 5 6 2 9 1 3 8
5 6 9 1 3 8 2 4 7
6 5 1 7 4 2 8 9 3
7 4 6 3 8 5 9 1 2
8 3 7 9 6 4 5 2 1
9 1 8 2 7 3 6 5 4</pre>
'''Tasks'''
<lang haskell>task1 = do
putStrLn "Latin squares of order 4:"
mapM_ printTable $ latinSquares [1..4]
task2 = do
putStrLn "Sizes of latin squares sets for different orders:"
forM_ [1..6] $ \n ->
let size = length $ latinSquares [1..n]
total = fact n * fact (n-1) * size
fact i = product [1..i]
in printf "Order %v: %v*%v!*%v!=%v\n" n size n (n-1) total</lang>
<pre>λ> task1 >> task2
Latin squares of order 4:
1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1
1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1
1 2 3 4
2 1 4 3
4 3 1 2
3 4 2 1
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
Sizes of latin squares sets for different orders:
Order 1: 1*1!*0!=1
Order 2: 1*2!*1!=2
Order 3: 1*3!*2!=12
Order 4: 4*4!*3!=576
Order 5: 56*5!*4!=161280
Order 6: 9408*6!*5!=812851200</pre>
=={{header|Java}}==
| |||