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.

Improve this question
$\endgroup$
5
  • $\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
    Commented Feb 5, 2019 at 10:24
  • $\begingroup$ I'm not sure how "input from keyboard" makes any difference. $\endgroup$
    – Yuval Filmus
    Commented Feb 5, 2019 at 15:33
  • $\begingroup$ What do you call a permutation of a multidimensional array ?? $\endgroup$
    – user16034
    Commented Feb 5, 2019 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
    Commented Feb 5, 2019 at 21:16
  • $\begingroup$ Different fillings won’t produce the same permutations, since they have different histograms. $\endgroup$
    – Yuval Filmus
    Commented Feb 6, 2019 at 3:11

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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