On counting and generating all $k$-permutations of a multiset

Solution 1:

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).