What is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array?
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 &lt; i_2 &lt; \cdots &lt; 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).