# What is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array?

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.

• 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. Feb 5 '19 at 10:24
• I'm not sure how "input from keyboard" makes any difference. Feb 5 '19 at 15:33
• What do you call a permutation of a multidimensional array ?? Feb 5 '19 at 16:31
• @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? Feb 5 '19 at 21:16
• Different fillings won’t produce the same permutations, since they have different histograms. Feb 6 '19 at 3:11

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