Let $A$ be a finite set, and $\mu:A \to \mathbb{N}_{>0}$. Let $M$ be the multiset having $A$ as its "underlying set of elements" and $\mu$ as its "multiplicity function". (Hence $M$ is finite.)
Let $0 \leq k \leq \left|M\right|$ be an integer.
This question is about the set $\mathbf{P}(M, k)$ of all $k$-permutations of elements from the multiset $M$.
For example, if $k = 3$ and $M$ is the multiset $\{0, 0, 1, 2\}$, then $\mathbf{P}(M, k)$ comprises these 12 $k$-permutations:
$$ (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 2), (0, 2, 0), (0, 2, 1), \\ (1, 0, 0), (1, 0, 2), (1, 2, 0), (2, 0, 0), (2, 0, 1), (2, 1, 0) $$
I am interested in
- an efficient (and preferably non-recursive) algorithm for generating all the elements of $\mathbf{P}(M, k)$ (in any order);
- a way to determine the cardinality of the set $\mathbf{P}(M, k)$ without generating all its elements (IOW, without resorting to the solution of (1)).
(I had no trouble coming up with a recursive algorithm to generate all the elements of $\mathbf{P}(M, k)$, but it is impractical, for two reasons, both having to do with my algorithm's recursive structure: (1) its space requirements grow very rapidly with $\left|A\right|$, and (2) there is no simple way to implement it so that it can be "gracefully interrupted" (e.g. in an interactive setting)1. These two shortcomings are not independent: the severity of (1) is what makes the interruptibility mentioned in (2) desirable.)
My guess is that a fair bit of work has been done on this problem, but all the searches I've tried are swamped by hits pointing to similar-sounding but substantially different problems. (Many of these false hits turn out to be easier special cases of the problem described here.) Similarly, I spent some time flipping through Stanley's Enumerative Combinatorics, v. 1, but I was not able to find what I was looking for (even though odds are that the problem is discussed somewhere in this work).
Therefore, in lieu of answers to 1 and 2 above, I could also use
- search keywords that will lead to the prior work on this problem; (in particular, is there a name for the integers $\mathbf{P}(M, k)$?)
1By this I mean that the computation can be aborted (e.g. through some user-initiated signal or some pre-configured time-out) without having to bring down the entire process.