0
$\begingroup$

There is D-dimensional array A. The number D and the size Sd of every dimension d=1..D is input from keyboard. There is also 1-dimensional array E of size N. It consists of unique integer numbers 0..N-1. N is also input from keyboard.

First we need to fill A with elements of E so that every element is presented at least once (see comment on this). Then we need to generate all possible permutations of A. Every unique permutation (transpositions are considered as unique permutations) need to be stored in a file.

Please explain what algorithms/theoretical methods will be helpful here. I need the fastest possible solution (minimum time-complexity). Is there a way of counting the number of all possible permutations first? I will be really grateful for the pseudocode.

Comment: If there are several fillings possible, we need to work with all of them (this happens when N < S1*S2*..*SD). If there is impossible to fill an array (N > S1*S2*..*SD) the error need to be returned.

$\endgroup$
  • $\begingroup$ First generate all possible ways to fill your array in nondecreasing order in such a way that all symbols occur; it is standard to count and enumerate all such ways. Then go over all permutations of each - another standard task. $\endgroup$ – Yuval Filmus Feb 5 at 10:24
  • $\begingroup$ I'm not sure how "input from keyboard" makes any difference. $\endgroup$ – Yuval Filmus Feb 5 at 15:33
  • $\begingroup$ What do you call a permutation of a multidimensional array ?? $\endgroup$ – Yves Daoust Feb 5 at 16:31
  • $\begingroup$ @YuvalFilmus "First generate..." -- Do I understand correctly that the best way to go over all permutations of a multidimensional array is to map it into 1d-array with index math and then go over all permutations of that array with lexicographical sorting method? This way we'll have S! permutations for each filling. And we need to go over all fillings also. But shouldn't different fillings produce the same permutations sometimes as the elements may duplicate? Is there a way to take it into consideration? $\endgroup$ – layer19 Feb 5 at 21:16
  • $\begingroup$ Different fillings won’t produce the same permutations, since they have different histograms. $\endgroup$ – Yuval Filmus Feb 6 at 3:11
0
$\begingroup$

It is well-known that the number of non-negative integer solutions to $x_1+\dots+x_a = b$ is $\binom{a+b-1}{a-1}$, and the number of positive integer solutions is $\binom{b-1}{a-1}$. To see the latter, notice that a set $1 \leq i_1 < i_2 < \cdots < i_{a-1} \leq b-1$ corresponds to the solution $x_1 = i_1$, $x_2 = i_2 - 1$, ..., $x_{a-1} = i_{a-1} - i_{a-2}$, $x_a = b - i_{a-1}$.

Therefore the number of ways to fill your array is $$ \binom{S-1}{N-1} \cdot S!, \text{ where } S = S_1 S_2 \cdots S_D. $$ Indeed, if you sort each filling then you get $x_i$ many $i$'s for $0 \leq i \leq N-1$, where $x_i \geq 1$ and $\sum_i x_i = S$.

You can generate all the fillings by first generating all solutions to $x_0 + \cdots + x_{N-1} = S$ (which you can do recursively, for example, or using an algorithm for generating all subsets of $[S-1]$ of size $[N-1]$, and converting each subset to a solution in the obvious way), filling the array in nondecreasing order accordingly, and then generating all permutations (a well-known problem).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.