Ordered partitions: Difference between revisions
(Create Page and add task description) |
(Improve task/layout and add Haskell solutions) |
||
Line 1: | Line 1: | ||
{{task|Discrete math}} |
{{task|Discrete math}} |
||
In this task we want to find the ordered partitions into fixed-size blocks. |
In this task we want to find the ordered partitions into fixed-size blocks. This task is related to [Combinations] in that it has to do with discrete mathematics and moreover a helper function to compute combinations is (probably) needed to solve this task. |
||
<code>partitions(arg1,arg2,...,argn)</code> should generate all distributions of the |
<code>partitions(arg1,arg2,...,argn)</code> should generate all distributions of the |
||
Line 44: | Line 44: | ||
that the sought function receives. The operator <code>#</code> returns the number of |
that the sought function receives. The operator <code>#</code> returns the number of |
||
elements in a set, e.g. <code>#{1,2,3} = 3</code>. <code>()</code> is a tuple, e.g. <code>(1,2,3)</code>. |
elements in a set, e.g. <code>#{1,2,3} = 3</code>. <code>()</code> is a tuple, e.g. <code>(1,2,3)</code>. |
||
__TOC__ |
|||
=={{header|Haskell}}== |
|||
<lang haskell> |
|||
comb :: Int -> [a] -> [[a]] |
|||
comb 0 _ = [[]] |
|||
comb _ [] = [] |
|||
comb k (x:xs) = [ x:cs | cs <- comb (k-1) xs ] ++ comb k xs |
|||
partitions :: [Int] -> [[[Int]]] |
|||
partitions xs = p [1..sum xs] xs |
|||
where p _ [] = [[]] |
|||
p xs (k:ks) = [ cs:rs | cs <- comb k xs, rs <- p (xs `minus` cs) ks ] |
|||
minus xs ys = [ x | x <- xs, not $ x `elem` ys ] |
|||
main = do putStrLn $ show $ partitions [2,0,2] |
|||
</lang> |
|||
An alternative where <code>minus</code> is not needed anymore because <code>comb</code> now not only |
|||
keeps the chosen elements but also the not chosen elements together in a tuple. |
|||
<lang haskell> |
|||
comb :: Int -> [a] -> [([a],[a])] |
|||
comb 0 xs = [([],xs)] |
|||
comb _ [] = [] |
|||
comb k (x:xs) = [ (x:cs,zs) | (cs,zs) <- comb (k-1) xs ] ++ |
|||
[ (cs,x:zs) | (cs,zs) <- comb k xs ] |
|||
partitions :: [Int] -> [[[Int]]] |
|||
partitions xs = p [1..sum xs] xs |
|||
where p _ [] = [[]] |
|||
p xs (k:ks) = [ cs:rs | (cs,zs) <- comb k xs, rs <- p zs ks ] |
|||
main = do putStrLn $ show $ partitions [2,0,2] |
|||
</lang> |
Revision as of 14:54, 7 February 2011
You are encouraged to solve this task according to the task description, using any language you may know.
In this task we want to find the ordered partitions into fixed-size blocks. This task is related to [Combinations] in that it has to do with discrete mathematics and moreover a helper function to compute combinations is (probably) needed to solve this task.
partitions(arg1,arg2,...,argn)
should generate all distributions of the
elements in {1,...,sum{arg1,arg2,...,argn}}
into #{arg1,arg2,...,argn}
blocks of respective size arg1,arg2,...,argn
.
E.g. partitions(2,0,2)
would create:
{({1, 2}, {}, {3, 4}), ({1, 3}, {}, {2, 4}), ({1, 4}, {}, {2, 3}), ({2, 3}, {}, {1, 4}), ({2, 4}, {}, {1, 3}), ({3, 4}, {}, {1, 2})}
E.g. partitions(1,1,1)
would create:
{({1}, {2}, {3}), ({1}, {3}, {2}), ({2}, {1}, {3}), ({2}, {3}, {1}), ({3}, {1}, {2}), ({3}, {2}, {1})}
Note that the number of elements in the list is
(arg1+arg2+...+argn choose arg1) * (arg2+arg3+...+argn choose arg2) * ... * (argn choose argn)
(i.e. the multinomial coefficient). Also, partitions(1,1,1)
creates the permutations of {1,2,3}
and thus there would be 3! = 6
elements in the list.
Note: Do not use functions that are not in the standard library of the
programming language you use. Your file should be written so that it can
be executed on the command line and by default outputs the result of
partitions(2,0,2)
. If the programming language does not support polyvariadic
functions pass a list as an argument.
Notation
Remarks on the used notation for the task in order to understand it easierly.
{1,...,n}
denotes the set of consecutive numbers from 1
to n
, e.g.
{1,2,3}
if n = 3
. sum
is the function that takes as its sole argument
a set of natural numbers and computes the sum of the numbers, e.g.
sum{1,2,3} = 6
. arg1,arg2,...,argn
are the arguments - natural numbers -
that the sought function receives. The operator #
returns the number of
elements in a set, e.g. #{1,2,3} = 3
. ()
is a tuple, e.g. (1,2,3)
.
Haskell
<lang haskell> comb :: Int -> [a] -> a comb 0 _ = [[]] comb _ [] = [] comb k (x:xs) = [ x:cs | cs <- comb (k-1) xs ] ++ comb k xs
partitions :: [Int] -> [[[Int]]] partitions xs = p [1..sum xs] xs
where p _ [] = [[]] p xs (k:ks) = [ cs:rs | cs <- comb k xs, rs <- p (xs `minus` cs) ks ] minus xs ys = [ x | x <- xs, not $ x `elem` ys ]
main = do putStrLn $ show $ partitions [2,0,2] </lang>
An alternative where minus
is not needed anymore because comb
now not only
keeps the chosen elements but also the not chosen elements together in a tuple.
<lang haskell> comb :: Int -> [a] -> [([a],[a])] comb 0 xs = [([],xs)] comb _ [] = [] comb k (x:xs) = [ (x:cs,zs) | (cs,zs) <- comb (k-1) xs ] ++
[ (cs,x:zs) | (cs,zs) <- comb k xs ]
partitions :: [Int] -> [[[Int]]] partitions xs = p [1..sum xs] xs
where p _ [] = [[]] p xs (k:ks) = [ cs:rs | (cs,zs) <- comb k xs, rs <- p zs ks ]
main = do putStrLn $ show $ partitions [2,0,2] </lang>