Ordered partitions: Difference between revisions

Line 1:

~~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.

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.

<math>partitions(\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n)</math> should generate all distributions of the elements in <math>\{1,...,\Sigma_{i=1}^n\mathit{arg}_i\}</math> into <math>n</math> blocks of respective size <math>\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n</math>.

Line 29:

Line 32:

:<math>{\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}</math>

(see [http://en.wikipedia.org/wiki/Binomial_coefficient 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 [http://en.wikipedia.org/wiki/Multinomial_coefficient multinomial coefficient]). ~~Also, <math>partitions(1,1,1)</math> creates the permutations of <math>\{1,2,3\}</math> and thus there would be <math>3! = 6</math> elements in the list.~~

(i.e. the [http://en.wikipedia.org/wiki/Multinomial_coefficient multinomial coefficient]).

Also, <math>partitions(1,1,1)</math> creates the permutations of <math>\{1,2,3\}</math> and thus there would be <math>3! = 6</math> 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 <math>partitions(2,0,2)</math>. If the programming language does not support polyvariadic functions pass a list as an argument.

Line 37:

Line 42:

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

<math>\{1, \ldots, n\}</math> denotes the set of consecutive numbers from <math>1</math> to <math>n</math>, e.g. <math>\{1,2,3\}</math> if <math>n = 3</math>. <math>\Sigma</math> is the mathematical notation for summation, e.g. <math>\Sigma_{i=1}^3 i = 6</math> (see also [http://en.wikipedia.org/wiki/Summation#Capital-sigma_notation]). <math>\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n</math> are the arguments — natural numbers — that the sought function receives.

<math>\{1, \ldots, n\}</math> denotes the set of consecutive numbers from <math>1</math> to <math>n</math>, e.g. <math>\{1,2,3\}</math> if <math>n = 3</math>.

<math>\Sigma</math> is the mathematical notation for summation, e.g. <math>\Sigma_{i=1}^3 i = 6</math> (see also [http://en.wikipedia.org/wiki/Summation#Capital-sigma_notation]).

<math>\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n</math> are the arguments — natural numbers — that the sought function receives.

=={{header|Ada}}==