Ordered partitions

Ordered partitions
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({\mathit {arg}}_{1},{\mathit {arg}}_{2},...,{\mathit {arg}}_{n})$ should generate all distributions of the elements in $\{1,...,\Sigma _{i=1}^{n}{\mathit {arg}}_{i}\}$ into $n$ blocks of respective size ${\mathit {arg}}_{1},{\mathit {arg}}_{2},...,{\mathit {arg}}_{n}$.

Example 1: $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})}

Example 2: $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

${{\mathit {arg}}_{1}+{\mathit {arg}}_{2}+...+{\mathit {arg}}_{n} \choose {\mathit {arg}}_{1}}\cdot {{\mathit {arg}}_{2}+{\mathit {arg}}_{3}+...+{\mathit {arg}}_{n} \choose {\mathit {arg}}_{2}}\cdot \ldots \cdot {{\mathit {arg}}_{n} \choose {\mathit {arg}}_{n}}$

(see the definition of the binomial coefficient if you are not familiar with this notation) and the number of elements remains the same regardless of how the argument is permuted (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,\ldots ,n\}$ denotes the set of consecutive numbers from $1$ to $n$, e.g. $\{1,2,3\}$ if $n=3$. $\Sigma$ is the mathematical notation for summation, e.g. $\Sigma _{i=1}^{3}i=6$ (see also [1]). ${\mathit {arg}}_{1},{\mathit {arg}}_{2},...,{\mathit {arg}}_{n}$ are the arguments — natural numbers — that the sought function receives.

D

Translation of: Python

Using code from this lexicographical Combination. <lang d>import std.stdio, std.algorithm, std.range, std.array, std.conv ; import comblex ;

alias int[] iRNG ;

auto setDiff(iRNG s, iRNG c) { return array(setDifference(s,c)) ; }

iRNG[][] orderPart(iRNG blockSize ...) {

   iRNG sum = array(iota(1, 1 + reduce!"a+b"(blockSize))) ;

   iRNG[][] p(iRNG s, iRNG b) {
       if(b.length == 0) return [[]] ;
       iRNG[][] res ;
       foreach(c ; Comb.On(s, b[0]))
           foreach(r ; p(setDiff(s, c), b[1..$]))
               res ~= (c.dup ~ r) ;
       return res ;
   }

   return p(sum, blockSize) ;

}

void main(string[] args) {

   auto b = args.length > 1 ? array(map!(to!int)(args[1..$])) : [2,0,2] ;  
   foreach(p;orderPart(b))
       writeln(p) ;

}</lang> Output:

[[1, 2], , [3, 4]]
[[1, 3], , [2, 4]]
[[1, 4], , [2, 3]]
[[2, 3], , [1, 4]]
[[2, 4], , [1, 3]]
[[3, 4], , [1, 2]]

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>

Output:

[[[1,2],[],[3,4]],[[1,3],[],[2,4]],[[1,4],[],[2,3]],[[2,3],[],[1,4]],[[2,4],[],[1,3]],[[3,4],[],[1,2]]]

J

Brute force approach:

<lang j>require'stats' partitions=: ([,] {L:0 (i.@#@, -. [)&;)/"1@>@,@{@({@comb&.> +/\.)</lang>

First we compute each of the corresponding combinations for each argument, then we form their cartesian product and then we restructure each of those products by: eliminating from values populating the the larger set combinations the combinations already picked from the smaller set and using the combinations from the larger set to index into the options which remain.

Examples:

<lang j> partitions 2 0 2 ┌───┬┬───┐ │0 1││2 3│ ├───┼┼───┤ │0 2││1 3│ ├───┼┼───┤ │0 3││1 2│ ├───┼┼───┤ │1 2││0 3│ ├───┼┼───┤ │1 3││0 2│ ├───┼┼───┤ │2 3││0 1│ └───┴┴───┘

  partitions 1 1 1

┌─┬─┬─┐ │0│1│2│ ├─┼─┼─┤ │0│2│1│ ├─┼─┼─┤ │1│0│2│ ├─┼─┼─┤ │1│2│0│ ├─┼─┼─┤ │2│0│1│ ├─┼─┼─┤ │2│1│0│ └─┴─┴─┘

  #partitions 2 3 5

2520

  #partitions 5 7 11

|out of memory: partitions | # partitions 5 7 11

  */ (! +/\.)5 7 11

1070845776

  #partitions 3 5 7

360360

  */ (! +/\.)3 5 7

360360</lang>

Lua

A pretty verbose solution. Maybe somebody can replace with something terser/better. <lang lua>--- Create a list {1,...,n}. local function range(n)

 local res = {}
 for i=1,n do
   res[i] = i
 end
 return res

end

--- Return true if the element x is in t. local function isin(t, x)

 for _,x_t in ipairs(t) do
   if x_t == x then return true end
 end
 return false

end

--- Return the sublist from index u to o (inclusive) from t. local function slice(t, u, o)

 local res = {}
 for i=u,o do
   res[#res+1] = t[i]
 end
 return res

end

--- Compute the sum of the elements in t. -- Assume that t is a list of numbers. local function sum(t)

 local s = 0
 for _,x in ipairs(t) do
   s = s + x
 end
 return s

end

--- Generate all combinations of t of length k (optional, default is #t). local function combinations(m, r)

 local function combgen(m, n)
   if n == 0 then coroutine.yield({}) end
   for i=1,#m do
     if n == 1 then coroutine.yield({m[i]})
     else
       for m0 in coroutine.wrap(function() combgen(slice(m, i+1, #m), n-1) end) do
         coroutine.yield({m[i], unpack(m0)})
       end
     end
   end
 end
 return coroutine.wrap(function() combgen(m, r) end)

end

--- Generate a list of partitions into fized-size blocks. local function partitions(...)

 local function helper(s, ...)
   local args = {...}
   if #args == 0 then return {% templatetag openvariable %}{% templatetag closevariable %} end
   local res = {}
   for c in combinations(s, args[1]) do
     local s0 = {}
     for _,x in ipairs(s) do if not isin(c, x) then s0[#s0+1] = x end end
     for _,r in ipairs(helper(s0, unpack(slice(args, 2, #args)))) do
       res[#res+1] = {{unpack(c)}, unpack(r)}
     end
   end
   return res
 end
 return helper(range(sum({...})), ...)

end

-- Print the solution io.write "[" local parts = partitions(2,0,2) for i,tuple in ipairs(parts) do

 io.write "("
 for j,set in ipairs(tuple) do
   io.write "{" 
   for k,element in ipairs(set) do
     io.write(element)
     if k ~= #set then io.write(", ") end
   end
   io.write "}"
   if j ~= #tuple then io.write(", ") end
 end
 io.write ")"
 if i ~= #parts then io.write(", ") end

end io.write "]" io.write "\n"</lang>

Output:

[({1, 2}, {}, {3, 4}), ({1, 3}, {}, {2, 4}), ({1, 4}, {}, {2, 3}), ({2, 3}, {}, {1, 4}), ({2, 4}, {}, {1, 3}), ({3, 4}, {}, {1, 2})]

Python

<lang python>from itertools import combinations

def partitions(*args):

   def p(s, *args):
       if not args: return [[]]
       res = []
       for c in combinations(s, args[0]):
           s0 = [x for x in s if x not in c]
           for r in p(s0, *args[1:]):
               res.append([c] + r)
       return res
   s = range(sum(args))
   return p(s, *args)

print partitions(2, 0, 2)</lang>

An equivalent but terser solution. <lang python>from itertools import combinations as comb

def partitions(*args):

   def minus(s1, s2): return [x for x in s1 if x not in s2]
   def p(s, *args):
       if not args: return [[]]
       return [[c] + r for c in comb(s, args[0]) for r in p(minus(s, c), *args[1:])]
   return p(range(1, sum(args) + 1), *args)

print partitions(2, 0, 2)</lang>

Output:

[[(0, 1), (), (2, 3)], [(0, 2), (), (1, 3)], [(0, 3), (), (1, 2)], [(1, 2), (), (0, 3)], [(1, 3), (), (0, 2)], [(2, 3), (), (0, 1)]]

Tcl

Library: Tcllib (Package: struct::set)

<lang tcl>package require Tcl 8.5 package require struct::set

1. Selects all k-sized combinations from a list.
2. "Borrowed" from elsewhere on RC

proc selectCombinationsFrom {k l} {

   if {$k == 0} {return {}} elseif {$k == [llength $l]} {return [list $l]}
   set all {}
   set n [expr {[llength $l] - [incr k -1]}]
   for {set i 0} {$i < $n} {} {
       set first [lindex $l $i]

incr i

       if {$k == 0} {
           lappend all $first

} else { foreach s [selectCombinationsFrom $k [lrange $l $i end]] { lappend all [list $first {*}$s] }

       }
   }
   return $all

}

1. Construct the partitioning of a given list

proc buildPartitions {lst n args} {

   # Base case when we have no further partitions to process
   if {[llength $args] == 0} {

return [list [list $lst]]

   }
   set result {}
   set c [selectCombinationsFrom $n $lst]
   if {[llength $c] == 0} {set c [list $c]}
   foreach comb $c {

# Sort necessary for "nice" order set rest [lsort -integer [struct::set difference $lst $comb]] foreach p [buildPartitions $rest {*}$args] { lappend result [list $comb {*}$p] }

   }
   return $result

}

1. Wrapper that assembles the initial list and calls the partitioner

proc partitions args {

   set sum [tcl::mathop::+ {*}$args]
   set startingSet {}
   for {set i 1} {$i <= $sum} {incr i} {

lappend startingSet $i

   }

   return [buildPartitions $startingSet {*}$args]

}</lang> Demonstration code: <lang tcl>puts [partitions 1 1 1] puts [partitions 2 2] puts [partitions 2 0 2] puts [partitions 2 2 0]</lang> Output:

{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}
{{1 2} {3 4}} {{1 3} {2 4}} {{1 4} {2 3}} {{2 3} {1 4}} {{2 4} {1 3}} {{3 4} {1 2}}
{{1 2} {} {3 4}} {{1 3} {} {2 4}} {{1 4} {} {2 3}} {{2 3} {} {1 4}} {{2 4} {} {1 3}} {{3 4} {} {1 2}}
{{1 2} {3 4} {}} {{1 3} {2 4} {}} {{1 4} {2 3} {}} {{2 3} {1 4} {}} {{2 4} {1 3} {}} {{3 4} {1 2} {}}