Here is an algorithm that can sort in exactly $d$ steps ($d$ permutations). It uses only the so-called $2$nd subset, where all operations bring the last entry (the $d$) to the front, while allowing you to "shoot" the front entry (the $0$) anywhere.
My key idea is that, the power to move $0$ anywhere makes this similar to how one can sort a hand of cards. I.e. maintain a sorted sub-sequence, and at every step take a new card and insert it into the right place in the sorted sub-sequence, growing the sorted sub-sequence by one card. After inserting $d$ cards you'd be done. It took me a few tries to get all the details right, to map this onto the $2$nd subset.
Here is my first attempt:
Initialization: Color the $2$nd entry (i.e. position $1$ in your numbering scheme) in the input array red. (This step is conceptual - no permutation is actually done.)
Invariant: In between turns, the red entries will always start at the second position (position $1$), be contiguous, and be sorted.
Every turn: Pick the $1$st entry (position $0$), which will be not red. Color it red, and insert it into the existing red sub-array at the right place.
Here is an example: We will sort $FCBDGEA$.
$$
\begin{align}
FCBDGEA & = F\color{red}{C}BDGEA \, \, \, \, \, \, \text{(initialization)}\\
& \rightarrow A\color{red}{CF}BDGE \\
& \rightarrow E\color{red}{ACF}BDG \\
& \rightarrow G\color{red}{ACEF}BD \\
& \rightarrow D\color{red}{ACEFG}B \\
& \rightarrow B\color{red}{ACDEFG} \\
& \rightarrow \color{red}{GABCDEF} \\
\end{align}
$$
Clearly (e.g. by the invariant), after $d$ turns (i.e. $d$ permutations) we end up with the sorted array, but starting at the $2$nd position. I.e., the result is one left-shift from the desired answer. Left-shift is not allowed, but right-shift is in the $2$nd subset, so we can do $d$ more right-shifts and arrive at the desired answer $ABCDEFG$. Therefore this first-attempt runs in $2d$ steps.
My second attempt fixes the "bug" by declaring that the minimum element (here, $A$) be treated as the maximum. Except for this modified sort order, the algorithm is identical to the first attempt. The same example:
$$
\begin{align}
FCBDGEA & = F\color{red}{C}BDGEA \, \, \, \, \, \, \text{(initialization)}\\
& \rightarrow A\color{red}{CF}BDGE \\
& \rightarrow E\color{red}{CFA}BDG \, \, \, \, \, \, \text{(treat $A$ as maximum)}\\
& \rightarrow G\color{red}{CEFA}BD \\
& \rightarrow D\color{red}{CEFGA}B \\
& \rightarrow B\color{red}{CDEFGA} \\
& \rightarrow \color{red}{ABCDEFG} \\
\end{align}
$$
Just like in the first attempt, after $d$ steps (permutations) we end up with the "sorted" array starting at the $2$nd position - except now "sorted" means according to the "modified" sort order, i.e. $BCDEFGA$. Clearly, this means the array starting at the front will be sorted according to the unmodified order. I.e. this second attempt algorithm sorts the array in exactly $d$ steps (permutations), as claimed.
Let $E_{m}(x)=\sum_{j=0}^m x^j/j!$ be the $m^{th}$ partial sum of the exponential series. If a multiset $M$ has $r$ distinct elements, where the first element is repeated $n_1$ times, the second $n_2$ times, etc, then the number of ways to choose an ordered list consisting of $k$ elements of $M$ is equal to
$$
k![x^k]\prod_{i=1}^rE_{n_i}(x).\tag{*}
$$
Here, $[x^k]f(x)$ denotes the coefficient of $x^k$ in the polynomial $f(x)$.
For example, consider the multiset $\{a,a,b,c\}$ from your post. There are $3$ distinct elements, the first, $a$, appearing $n_1=2$ times, and the latter two, $b$ and $c$, appearing $n_2=n_3=1$ time. The product of the partial exponential sums in $(*)$ is therefore
\begin{align}
E_{2}(x)\cdot E_1(x)\cdot E_1(x)
&=(1+x+x^2/2)\cdot(1+x)\cdot(1+x)
\\&=1+3x+\frac{7}2x^2+2x^3+\frac12x^4
\\&=1+\frac{\color{red}3}{1!}x+\frac{\color{red}7}{2!}x^2+\frac{\color{red}{12}}{3!}x^3+\frac{\color{red}{12}}{4!}x^4\end{align}
Notice that the coefficients of this polynomial correspond to the answer to your combinatorial question $(3,7,12,12)$, divided by an appropriate factorial.
The techniques used in this post are more widely known as exponential generating functions. For more of an explanation on why this works, see generatingfunctionology by Herbert Wilf, especially chapter 3 on exponential generating functions. It is available for free online.
Best Answer
Once the numbers in the array have been chosen, there is only one possible array, because there is only one way to sort them. So the number of arrays is just the number of $k$-element subsets of $\{1,2,\dots,n\}$, that is, $\binom nk$.