On counting and generating all $k$-permutations of a multiset 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.
 A: Generating $k$-tuples from a multiset
The Question expresses concern a recursive generation of these combinatorial objects must suffer from "space requirements [that] grow very rapidly" with the size $|A|$ of the underlying set $A$ in which multiset $M$ takes its repetitions.  Let's first outline a method for generating these with reasonable space complexity.
Apart from some fixed amount of bookkeeping (pointers, etc.), the important structures are a working copy of the multiset (from which items may be removed and replaced) and a working copy of a $k$-tuple (modified successively to produce all $k$-permutations in ascending lexicographic order).
If the maximum repetition $\max \mu(A)$ is less than $2^b$, then the multiset $M$ can be represented by an unsigned integer array $R=[r_1,\ldots,r_a]$ of length $a=|A|$, whose entries (of bitsize $b$) correspond to repetition counts of the elements of $A$.  We may WLOG take $A=\{1,\ldots,a\}$, so the index of the (1-based) array matches the underlying element of $A$.
The $k$-permutations will be represented by successively populating a $k$-tuple $T = (i_1,\ldots,i_k)$ whose entries are indexes denoting elements of $A$.
As items from the multiset are used to form a $k$-tuple, we will "remove" them from $M$ by decrementing the respective entry of $R$.  Similarly if an item in the $k$-tuple is "replaced", it goes back in the pool and the entry is incremented.  Thus an updated status of the available pool of items can be maintained in array $R$.
The algorithm can be described as a recursion-with-backtracking or as an equivalent iterative procedure.  The recursive description is likely more concise.

To populate the $k$-tuple, choose the leftmost entry of $T$ successively from distinct least to greatest possible from the available pool $R$ and remove that item from the pool.  Populate the rest of the entries of $T$ by generating the possible $k-1$-tuples from the remaining items in the pool.  On backtracking (to the next larger choice of leftmost entry), update the pool with replacement of the previously chosen item and the removal of the new choice.

Example:  For the case $k=3$ and $M = \{1,1,2,3\}$, we can visualize the search tree as follows:
1st entry            2nd entry            3rd entry    k-tuple  
   1 ---------+-------- 1 ---------+-------- 2         (1,1,2)  
              |                    |                            
              |                    +-------- 3         (1,1,3)  
              |                                                 
              +-------- 2 ---------+-------- 1         (1,2,1)  
              |                    |                            
              |                    +-------- 3         (1,2,3)  
              |                                                 
              +-------- 3 ---------+-------- 1         (1,3,1)  
                                   |                            
                                   +-------- 2         (1,3,2)  

   2 ---------+-------- 1 ---------+-------- 1         (2,1,1)  
              |                    |                            
              |                    +-------- 3         (2,1,3)  
              |                                                 
              +-------- 3 ---------+-------- 1         (2,3,1)  

   3 ---------+-------- 1 ---------+-------- 1         (3,1,1)  
              |                    |                            
              |                    +-------- 2         (3,1,2)  
              |                                                 
              +-------- 2 ---------+-------- 1         (3,2,1)  

Thus all twelve $3$-permutations of multiset $\{1,1,2,3\}$ are found in ascending lexicographical order.
Prolog Implementation
Apart from the length/2 predicate, almost universally provided either as a built-in or library predicate, the following is a self-contained implementation of the recursion-with-backtracking algorithm described above:
/*
    kPermute(++K,++Multiples,?Ktuple)

    Takes instantiated integer K > 0
    and list of multiplicities Multiples
    of length n denoting repeated items
    in the underlying set A = {1,..,n}.

    Generates by backtracking lists Ktuple
    of length K whose entries lie in A.
*/
kPermute(K,Multiples,Ktuple) :-
    length(Ktuple,K),
    kTuple(Multiples,Ktuple).

/* kTuple(++Multiples,+Ktuple) */
kTuple(_,[ ]).
kTuple(M,[K|Tuple]) :-
    removeItem(M,K,R,1),
    kTuple(R,Tuple).

/* removeItem(++List,-Item,-Remnant,++Index) */
removeItem([H|T],I,[G|T],I) :-
    H > 0,
    G is H-1.
removeItem([H|T],I,[H|R],J) :-
    K is J+1,
    removeItem(T,I,R,K).

A: I am not sure if this is still relevant, but I needed this myself so here is my (non-recursive) Python code in case anyone wants it:
def kpm(R, k):
    class P:
        def __init__(self, R):
            self.R = R
        def push(self, v):
            self.R[v] += 1
        # pops smallest value >= v if one exists
        # returns None otherwise
        def pop(self, v):
            while v < len(self.R):
                if self.R[v] > 0:
                    self.R[v] -= 1
                    return v
                v += 1
            return None

    pool = P(R)
    T = [None] * k
    t = 0

    while True:
        if T[t] is None:
            T[t] = pool.pop(0)
            if t < k - 1:
                t += 1
            else:
                print(T)
        else:
            pool.push(T[t])
            T[t] = pool.pop(T[t] + 1)
            if T[t] is None:
                if t > 0:
                    t -= 1
                else:
                    break
            else:
                if t < k - 1:
                    t += 1
                else:
                    print(T)

kpm([2,1,1], 3)

This generates
[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]

Edits: Minor optimizations
