If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our **Contribution Guidelines**.

# Generating Permutations with Repetition

Last modified: November 14, 2021

## 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 :

- If , then the only permutation is the empty one that we’ll denote as .
- 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:

### 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:

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 :

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