生成带重复的排列

1. Introduction

In this tutorial, we’ll present the recursive and iterative algorithms for generating permutations with repetition. Finding all permutations with repetition is a combinatorial problem like generating all -combinations of a set.

2. Permutations With Repetition

Permutations with repetition of a set are ordered tuples whose elements come from and may be repeated. If the tuples’ length is , we call them -tuples. For example, with and , the following are 4-tuples of :

   

Our task is to generate all the -tuples of a set . If , there are such tuples.

Here, we’ll take to be of the form . We don’t lose generality in doing so because we can map each set of elements to . So, we can map each -tuple of back to the elements of the original set.

To ease notation, we’ll write instead of .

3. Recursive Algorithm for Generating Permutations with Repetition

We can define permutations with repetition by induction over :

1. If , then the only permutation is the empty one that we’ll denote as .
2. If , then any -tuple can be obtained by prepending a number from to a -tuple.

These rules give us the logic to follow recursively. is the base case, and for each we prepend every to each tuple we got for .

3.1. Pseudocode

Here’s the pseudocode of the recursive solution:

algorithm Find(n, k):
    // INPUT
    //    n = the set cardinality
    //    k = the length of permutations with repetition
    // OUTPUT
    //    All the k-tuples of the set {1, 2, ..., n}

    if k = 0:
        return { [ ] }
    else:
        tuples_k_minus_1 <- Find(n, k-1)
        tuples_k <- empty set

        for tuple in tuples_k_minus_1:
            for i <- 1 to n:
                new_tuple <- prepend i to tuple
                tuples_k <- tuples_k + { new_tuple }

        return tuples_k

3.2. Example

Let’s see how the function works.  Let’s say that and that we want to find all the 3-tuples. The call returns 2-tuples:

   

To get -tuples, we first prepend 1 to all the 2-tuples and get:

   

Then, we prepend 2:

   

Then, after doing the same with 3, 4, and 5, we get all the 3-tuples.

4. Iterative Algorithm for Generating Permutations with Repetition

The recursive algorithm makes the -tuples available once it generates them all. That is, we can’t access any -tuple before generating all of them first. Since there are of them, the recursive algorithm’s space complexity is .  If our application is memory-constrained, this isn’t the way to go.

Moreover, we usually want to filter the permutations to keep only some of them. So, at any time of execution, we’ll be processing a single -tuple, which is why there’s no need for storing all the permutations. It would be best if we could do something like this:

• ask for a permutation
• process it and go to the previous step to ask for another -tuple

In that case, we’d need only space, which is a significant reduction compared to the recursive algorithm whose memory complexity grows exponentially with . We can achieve that with an algorithm that receives a permutation as its input and returns the next permutation in the lexicographic order. Let’s name that algorithm . Then, we start with the first permutation, and then, by calling , we iteratively generate and process all the other permutations:

algorithm IterativeAlgorithmForPermutationsWithRepetition(n, k):
    // INPUT
    //    n = the set cardinality
    //    k = the length of permutations with repetition
    // OUTPUT
    //    All the k-tuples of the set {1,2,...,n} are processed

    x <- [1, 1, ..., 1] // make the first permutation

    while x != failure:
        Process x
        x <- Next(x, n, k)

So, should return the next permutation if there is one, and if we ask it for the last -tuple’s successor. But, how do we implement ?

4.1. Generating the Next Permutation

This is the main idea. A permutation and its successor will have a common prefix. For example, with , is the successor of , and their common prefix is . The suffix that is different starts at the rightmost lower than . In this example, that was 4 in . We increment it by one and get .

However, this doesn’t cover all the cases. What if there’s an in the suffix we’re about to change? Let’s consider . The rightmost element lower than is 3. But, if we increment by 1, we get , whereas the actual successor is . So, what’s the correct logic?

The solution is to realize that the operation we should perform on every after is the circular increment. We increase by one all the numbers except , which we change to 1. But, if all the numbers are equal to , then there’s no successor. It’s the last permutation, so we should return to stop the caller’s loop.

4.2. Pseudocode

Here’s the pseudocode of :

algorithm Next(x, n, k):
    // INPUT
    //    x = the k-tuple of {1,2,...,n} to find the successor of
    //    n = the set cardinality
    //    k = the tuples' length
    // OUTPUT
    //    The lexicographic successor of x if it exists; failure if x is the last permutation.
    
    // Find the suffix to change.
    j <- k
    while j >= 1 and x[j] = n:
        j <- j - 1
        
    if j = 0:
        return failure  // x was the last permutation
        
    // Change the suffix.
    for ℓ <- j to k:
        if x[ℓ] = n:
            x[ℓ] <- 1
        else:
            x[ℓ] <- x[ℓ] + 1
            
    return x

As we see, apart from the auxiliary variables, doesn’t require more than memory to find the input’s successor.

4.3. Example

Let’s work out an example. Let’s say that and .

First, we determine where the suffix to change starts. The rightmost element lower than 7 is 2, so the suffix to change is . Next, we increment 2 by 1 to get 3 and replace all sevens with ones. The permutation we get is , which is the correct result.

It’s interesting to note that if we used as instead of , would amount to incrementing by 1 modulo .

5. Conclusion

In this article, we presented two ways to generate all the permutations with repetition of the set . The recursive algorithm returns all the permutations at once, whereas the iterative method processes them one by one and has a lower space complexity.