Generating Permutations with Repetition | Baeldung on Computer Science

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 $k$ -combinations of a set.

2. Permutations With Repetition

Permutations with repetition of a set $\boldsymbol{A}$ are ordered tuples whose elements come from $\boldsymbol{A}$ and may be repeated. If the tuples’ length is $k$ , we call them $k$ -tuples. For example, with $A=\{1,2,3,4,5,6,7\}$ and $k=4$ , the following are 4-tuples of $A$ :

$\begin{aligned} (1,1,1,1) \\ (1,2,3,4) \\ (5,4,2,2) \end{aligned}$

Our task is to generate all the $k$ -tuples of a set $A$ . If $|A|=n$ , there are $n^k$ such tuples.

Here, we’ll take $A$ to be of the form $\{1,2,\ldots, n\}$ . We don’t lose generality in doing so because we can map each set of $n$ elements to $\{1,2,\ldots,n\}$ . So, we can map each $k$ -tuple of $\{1,2,\ldots,n\}$ back to the elements of the original set.

To ease notation, we’ll write $1234$ instead of $(1,2,3,4)$ .

3. Recursive Algorithm for Generating Permutations with Repetition

We can define permutations with repetition by induction over $k$ :

If $k=0$ , then the only permutation is the empty one that we’ll denote as $[\ ]$ .
If $k > 0$ , then any $k$ -tuple can be obtained by prepending a number from $\{1,2,\ldots, n\}$ to a $(k-1)$ -tuple.

These rules give us the logic to follow recursively. $k = 0$ is the base case, and for each $k>0$ we prepend every $i \in \{1,2,\ldots,n\}$ to each tuple we got for $k-1$ .

3.1. Pseudocode

Here’s the pseudocode of the recursive solution:

3.2. Example

Let’s see how the $FIND$ function works. Let’s say that $n=5$ and that we want to find all the 3-tuples. The call $FIND(n, 2)$ returns $25$ 2-tuples:

$\begin{aligned} 11 && 12 && 13 && 14 && 15 \\ 21 && 22 && 23 && 24 && 25 \\ 31 && 32 && 33 && 34 && 35 \\ 41 && 42 && 43 && 44 && 45 \\ 51 && 52 && 53 && 54 && 55 \end{aligned}$

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

$\begin{aligned} 111 && 112 && 113 && 114 && 115 \\ 121 && 122 && 123 && 124 && 125 \\ 131 && 132 && 133 && 134 && 135 \\ 141 && 142 && 143 && 144 && 145 \\ 151 && 152 && 153 && 154 && 155 \\ \end{aligned}$

Then, we prepend 2:

$\begin{aligned} 211 && 212 && 213 && 214 && 215 \\ 221 && 222 && 223 && 224 && 225 \\ 231 && 232 && 233 && 234 && 235 \\ 241 && 242 && 243 && 244 && 245 \\ 251 && 252 && 253 && 254 && 255 \end{aligned}$

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

4. Iterative Algorithm for Generating Permutations with Repetition

The recursive algorithm makes the $k$ -tuples available once it generates them all. That is, we can’t access any $k$ -tuple before generating all of them first. Since there are $n^k$ of them, the recursive algorithm’s space complexity is $\boldsymbol{O(n^k)}$ . 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 $k$ -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 $k$ -tuple

In that case, we’d need only $O(k)$ space, which is a significant reduction compared to the recursive algorithm whose memory complexity grows exponentially with $k$ . 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 $NEXT$ . Then, we start with the first permutation, and then, by calling $NEXT$ , we iteratively generate and process all the other permutations:

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

4.1. Generating the Next Permutation

This is the main idea. A permutation $x=x_1x_2\ldot sx_k$ and its successor $x'=x_1'x_2'\ldots x_k'$ will have a common prefix. For example, with $n=7$ , $12735$ is the successor of $12734$ , and their common prefix is $1273$ . The suffix that is different starts at the rightmost $\boldsymbol{x_j}$ lower than $\boldsymbol{n}$ . In this example, that was 4 in $12734$ . We increment it by one and get $1235$ .

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

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

4.2. Pseudocode

Here’s the pseudocode of $NEXT$ :

As we see, apart from the auxiliary variables, $\boldsymbol{NEXT}$ doesn’t require more than $\boldsymbol{O(k)}$ memory to find the input’s successor.

4.3. Example

Let’s work out an example. Let’s say that $n=7$ and $x=x_1x_2\ldots x_5=12777$ .

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

It’s interesting to note that if we used $\boldsymbol{\{0,1,\ldots, n-1\}}$ as $\boldsymbol{A}$ instead of $\boldsymbol{\{1,2,\ldots, n\}}$ , $\boldsymbol{NEXT}$ would amount to incrementing by 1 modulo $\boldsymbol{n}$ .

5. Conclusion

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

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex