Problem Statement

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

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

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

would create: Note that the number of elements in the list is (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.

Let's start with the solution:

import algorithm, math, sequtils, strutils

type Partition = seq[seq[int]]


func isIncreasing(s: seq[int]): bool =
  ## Return true if the sequence is sorted in increasing order.
  var prev = 0
  for val in s:
    if prev >= val: return false
    prev = val
  result = true


iterator partitions(lengths: varargs[int]): Partition =
  ## Yield the partitions for lengths "lengths".

  # Build the list of slices to use for partitionning.
  var slices: seq[Slice[int]]
  var delta = -1
  var idx = 0
  for length in lengths:
    assert length >= 0, "lengths must not be negative."
    inc delta, length
    slices.add idx..delta
    inc idx, length

  # Build the partitions.
  let n = sum(lengths)
  var perm = toSeq(1..n)
  while true:

    block buildPartition:
      var part: Partition
      for slice in slices:
        let s = perm[slice]
        if not s.isIncreasing():
          break buildPartition
        part.add s
      yield part

    if not perm.nextPermutation():
      break


func toString(part: Partition): string =
  ## Return the string representation of a partition.
  result = "("
  for s in part:
    result.addSep(", ", 1)
    result.add '{' & s.join(", ") & '}'
  result.add ')'


when isMainModule:

  import os

  proc displayPermutations(lengths: varargs[int]) =
    ## Display the permutations.
    echo "Ordered permutations for (", lengths.join(", "), "):"
    for part in partitions(lengths):
      echo part.toString

  if paramCount() > 0:
    var args: seq[int]
    for param in commandLineParams():
      try:
        let val = param.parseInt()
        if val < 0: raise newException(ValueError, "")
        args.add val
      except ValueError:
        quit "Wrong parameter: " & param
    displayPermutations(args)

  else:
    displayPermutations(2, 0, 2)