5
$\begingroup$

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

  1. an efficient (and preferably non-recursive) algorithm for generating all the elements of $\mathbf{P}(M, k)$ (in any order);
  2. 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

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

$\endgroup$
5
  • $\begingroup$ Is there any difficulty with generating the k-tuples recursively in lexicographic order? $\endgroup$
    – hardmath
    Aug 13, 2015 at 13:09
  • $\begingroup$ @hardmath: I need to think about it... Naively, I would have expected that such an algorithm would, in general, produce some configurations more than once. On the other hand, if the generation happens in lexicographic order, I suppose that it would be relatively inexpensive to weed these duplicates out. I need to work out the details. Thanks for your suggestion. $\endgroup$
    – kjo
    Aug 13, 2015 at 14:07
  • 1
    $\begingroup$ Knuth's TAOCP vol4-fasc2b entitled "generating all permutations" may be a worthwhile document to scan through. $\endgroup$
    – kodlu
    Aug 14, 2015 at 0:07
  • 1
    $\begingroup$ A recent (Jurić and Šiljak, 2011) paper, A New Formula for the Number of Combinations and Permutations of Multisets appears relevant to the second task (counting $k$-permutations of a finite multiset without generating them all). $\endgroup$
    – hardmath
    Aug 14, 2015 at 1:13
  • $\begingroup$ General formula: math.stackexchange.com/questions/114654/… $\endgroup$ Jul 1, 2022 at 19:23

2 Answers 2

3
$\begingroup$

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).
$\endgroup$
3
  • $\begingroup$ Thanks! In the meantime I realized that the generation problem can be "factored" into two generation problems, arranged as an outer loop and an inner loop; the outer loop is the generation of all $k$-combinations (i.e. $k$-submultisets) from the multiset; the inner one is the generation of all the permutations of the current $k$-submultiset. There are many non-recursive algorithms for the inner loop generation. I have not found a non-recursive algorithm for the outer loop one, but I guess it would not be difficult to convert one of these to a relatively simple iteration, as you did here. $\endgroup$
    – kjo
    Aug 14, 2015 at 15:23
  • $\begingroup$ For information about generating (and counting) $k$-combinations of a multisets, Frank Ruskey's Combinatorial Generation (2003), Sec. 4.5.1 has an algorithm based on representing $k$-sub-multisets as compositions with restricted parts. $\endgroup$
    – hardmath
    Aug 14, 2015 at 16:09
  • $\begingroup$ The idea of working out the $k$-combinations, and then applying the "multinomial" logic to count $k$-permutations, also features in the paper by Jurić and Šiljak. I will give an account of their approach to the more difficult problem of counting $k$-permutations without generating all of them. $\endgroup$
    – hardmath
    Aug 14, 2015 at 16:11
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .