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.





p
a
r
t
i
t
i
o
n
s
(



a
r
g



1


,



a
r
g



2


,
.
.
.
,



a
r
g



n


)


{\displaystyle partitions({\mathit {arg}}_{1},{\mathit {arg}}_{2},...,{\mathit {arg}}_{n})}

 should generate all distributions of the elements in 



{
1
,
.
.
.
,

Σ

i
=
1


n





a
r
g



i


}


{\displaystyle \{1,...,\Sigma _{i=1}^{n}{\mathit {arg}}_{i}\}}

 into 



n


{\displaystyle n}

 blocks of respective size 






a
r
g



1


,



a
r
g



2


,
.
.
.
,



a
r
g



n




{\displaystyle {\mathit {arg}}_{1},{\mathit {arg}}_{2},...,{\mathit {arg}}_{n}}

.

Example 1: 



p
a
r
t
i
t
i
o
n
s
(
2
,
0
,
2
)


{\displaystyle 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: 



p
a
r
t
i
t
i
o
n
s
(
1
,
1
,
1
)


{\displaystyle 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








(






a
r
g



1


+



a
r
g



2


+
.
.
.
+



a
r
g



n






a
r
g



1




)



⋅



(






a
r
g



2


+



a
r
g



3


+
.
.
.
+



a
r
g



n






a
r
g



2




)



⋅
…
⋅



(





a
r
g



n





a
r
g



n




)





{\displaystyle {{\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, 



p
a
r
t
i
t
i
o
n
s
(
1
,
1
,
1
)


{\displaystyle partitions(1,1,1)}

 creates the permutations of 



{
1
,
2
,
3
}


{\displaystyle \{1,2,3\}}

 and thus there would be 



3
!
=
6


{\displaystyle 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 



p
a
r
t
i
t
i
o
n
s
(
2
,
0
,
2
)


{\displaystyle partitions(2,0,2)}

. If the programming language does not support polyvariadic functions pass a list as an argument.

Notation

Here are some explanatory remarks on the notation used in the task description:





{
1
,
…
,
n
}


{\displaystyle \{1,\ldots ,n\}}

 denotes the set of consecutive numbers from 



1


{\displaystyle 1}

 to 



n


{\displaystyle n}

, e.g. 



{
1
,
2
,
3
}


{\displaystyle \{1,2,3\}}

 if 



n
=
3


{\displaystyle n=3}

.





Σ


{\displaystyle \Sigma }

 is the mathematical notation for summation, e.g. 




Σ

i
=
1


3


i
=
6


{\displaystyle \Sigma _{i=1}^{3}i=6}

 (see also [1]).








a
r
g



1


,



a
r
g



2


,
.
.
.
,



a
r
g



n




{\displaystyle {\mathit {arg}}_{1},{\mathit {arg}}_{2},...,{\mathit {arg}}_{n}}

 are the arguments — natural numbers — that the sought function receives.




--- 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"