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.
Best Answer
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.
Example: For the case $k=3$ and $M = \{1,1,2,3\}$, we can visualize the search tree as follows:
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: