Permutations

Why it matters

Permutations appear in scheduling, puzzles, route planning and many interview questions. A permutation is one ordering of a list. A delivery driver who chooses the order of five stops is choosing one permutation. A puzzle that asks for every arrangement of letters is asking for all permutations. Permutations also teach the second main shape of backtracking. In subsets, each item had two choices, in or out. In permutations, each position has many choices, one for each item that has not been used yet. Once you can handle that shape cleanly, you can handle the N-Queens and sudoku problems in the last lesson of this module.

The idea: fill positions one at a time

Start with a small case. Three friends, Ana, Ben and Chi, sit in three chairs in a row. How many ways can they sit? Chair 1 can take any of the 3 friends. Once chair 1 is filled, chair 2 can take any of the remaining 2. Chair 3 gets the last friend, with no choice. The count is 3 times 2 times 1, which is 6.

This is the key picture. A permutation is a sequence of choices. Fill position 1, then position 2, then position 3. At each position, the choices are the items not used yet. The number of choices shrinks by one at each position. For n items the total is n times (n minus 1) times (n minus 2) and so on down to 1. That product is written n!, which you already met as factorial in the first lesson of this module.

The subsets lesson asked "in or out?" for each item. Permutations ask "which unused item goes in this position?" The decision tree is therefore wider than it is tall. The root has n children, one for each item that could go first. Each of those has n minus 1 children, and so on. Every leaf is one complete ordering.

Here is the tree for {1, 2, 3}. Each path from the root to a leaf is one permutation.

start
  pick 1
    pick 2 -> pick 3 -> 1 2 3
    pick 3 -> pick 2 -> 1 3 2
  pick 2
    pick 1 -> pick 3 -> 2 1 3
    pick 3 -> pick 1 -> 2 3 1
  pick 3
    pick 1 -> pick 2 -> 3 1 2
    pick 2 -> pick 1 -> 3 2 1

Permutation tree for three items: three choices at the first level, two at the second, and one at the third

The tree has 6 leaves, which matches 3 factorial. The picture also shows the rule for the recursion: at each node, the children are the unused items. The function must therefore know which items are used. There are two standard ways to do that, and this lesson shows both.

Version 1: a used array

The first version keeps a list of flags, one per item. A flag is true when the item is already in the current ordering. The vector cur holds the current ordering, built one item at a time. Its size tells you the position being filled.

No input is needed. The output is:

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

Each line has a trailing space, because the print loop writes a space after every value. Ignore it for now, and you will fix it in the repeated-values example later in this lesson.

Trace the first two lines. The first position tries item 1 first. It marks item 1 as used and pushes it, so cur is [1]. The second position tries item 1, finds it used, and skips it. It tries item 2, marks it used and pushes it, so cur is [1, 2]. The third position finds items 1 and 2 used, so it takes item 3. cur is now full, and the base case prints 1 2 3. Back in the second position, the loop moves on to item 3, which is unused. The undo removes item 2 from cur and clears its flag. Then item 3 is chosen, and the recursion completes 1 3 2.

Watch the picture of the call stack as the recursion makes its first complete path.

The stack has depth 3 at the deepest point, one frame per position. Each frame runs a loop. The loop is what makes permutations different from subsets, because each frame tries several choices instead of two.

Why the undo is two lines

Look at the end of the loop body. There are two undo lines, one for the vector and one for the flag. They are both needed. If you forget cur.pop_back(), the vector grows without limit and later permutations contain stale items. If you forget used[i] = false, the item stays marked as used after its branch is done, so later branches cannot use it, and some permutations are missing from the output.

Both undo lines restore the state from before the choice. That is the rule from the subsets lesson, and it is the reason backtracking works. The shared state at the start of each loop pass must match the state at the start of the previous pass. Only then is each branch explored from the same starting point.

Version 2: swap in place

The second version uses no extra arrays at all. It works on a string, and it keeps the answer in the string itself. The index start marks the position being filled. For each later item, the function swaps that item into position start, recurses to fill the next position, then swaps back.

No input is needed. The output is:

abc
acb
bac
bca
cba
cab

The order differs from version 1, but all six orderings appear. The reason is that the swap moves items around. After the first loop pass, the string is still abc, because the undo restored it. After the second pass the string is acb, because the swap of positions 1 and 2 happened and was not yet undone. The output depends on which item is swapped in first.

Trace the first pass. start is 0 and i is 0, so the swap changes nothing. The recursion with start at 1 has i equal to 1, so again nothing changes. Then start at 2 prints abc. Back at start 1 with i at 2, the swap exchanges b and c, giving acb, and the recursion prints acb. That undo restores abc. Back at start 0, the loop moves to i equal to 1, and the swap exchanges a and b, giving bac.

Notice that the loop starts at start, not at 0. That is important. Positions before start are already fixed by the earlier calls, so the loop must never move them. Starting at 0 would swap a fixed letter and produce wrong or repeated output. This is the most common error in this version.

Version 2 needs no used array, so its extra space is only the recursion depth, which is O(n). It works well for strings. For a vector, the same idea works with swap(a[start], a[i]).

Repeated values: the duplicate problem

Both versions treat each item as different, even when two items have the same value. For the input {1, 1, 2}, version 1 prints 1 1 2, 1 2 1, 2 1 1, and then 1 1 2, 1 2 1 and 2 1 1 again. That is six lines, but only three of them are different. The first 1 and the second 1 are interchangeable, so the arrangements repeat.

The fix has two parts. First, sort the input, so equal values sit next to each other. Second, in each loop, skip an item when it has the same value as the item just before it, and that earlier item is not used in the current path. The rule "not used in the current path" is the key. It makes the equal values be used in order, from left to right, so each arrangement is produced once.

Type this into the Input box and press Run:

3
1 1 2

The output is:

1 1 2
1 2 1
2 1 1

Three lines, each different. The sort puts the two 1s next to each other at indexes 0 and 1. When the loop is at index 1 and index 0 is still unused, the condition !used[i - 1] is true, and the skip fires. So the second 1 can be used only after the first 1 is in the path. That removes the duplicate that would have come from swapping two equal values.

Trace the branch that starts with the first 1. Index 0 is chosen, so cur is [1]. The next position tries index 1, which is also a 1. Index 0 is used, so the skip does not fire, and the 1 is chosen: cur is [1, 1]. Then the 2 is placed. That gives 1 1 2. Back in the second position, index 2 is tried, giving 1 2 1. Now go back to the first position and try index 1. It holds a 1 equal to index 0, and index 0 is not used at this point, because the loop has undone it. So index 1 is skipped. This is the duplicate case that is being prevented.

The standard library: next_permutation

C++ has a built-in function that produces the next permutation in dictionary order. It is std::next_permutation, and it works on any range with a sorted starting point. It returns true while a new ordering exists and false after the last one. Because it works through orderings in order and it skips equal values naturally, it handles duplicates with no extra rule.

Interviewers often ask you to write the recursion by hand, but in real code this function is the one to use. Knowing both is a good sign.

Type this into the Input box and press Run, using the same input as before:

3
1 1 2

The output is the same three lines as the recursive version, 1 1 2, 1 2 1 and 2 1 1. The loop starts with the sorted array, prints it, then asks for the next ordering. When there is no next ordering, next_permutation returns false and the loop ends.

The sort is required. If the array is not sorted, next_permutation walks only forward from where it starts, so some orderings are missed. The function does not sort for you. This is a classic trap: the output looks plausible but is incomplete.

The do ... while loop prints the first ordering before it asks for the next. A while loop would need the first ordering to be printed separately, so the do ... while shape fits this problem naturally.

Counting without printing: derangements

Not every permutation problem asks for the list. Many ask for a count, or a yes or no answer. A derangement is a permutation in which no item stays in its original place. For the list 1 to n, a derangement puts no value at its own position. For n equal to 3, the derangements are 2 3 1 and 3 1 2. The count of derangements of 4 items is 9.

This program counts derangements without printing a single list. It is a permutation with a rule on each position: the value placed at a position must not be the value that belongs there. The base case is a full permutation, which counts as one.

Type 4 into the Input box and press Run. The output is:

derangements of 4: 9

Check the nine by hand if you have time. The derangements of 1 to 4 are 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312 and 4321. Each one has no value in its own position. The count in the code agrees with the list.

This problem shows a useful habit. The recursion does not need to store the permutations. It counts the leaves that pass the test. The memory use is only the depth and the flags. When a question asks "how many," try to write the function that returns a count, and skip building the list.

The same pattern applies to other counting questions with a rule on each position. Count the arrangements where a particular item comes first. Count the arrangements where two items are never adjacent. In each case, the choice at each position follows the rule, and a branch that breaks the rule is skipped.

What happens inside the computer

Version 1 keeps used as a vector<bool>. This type is special. Ordinary bool takes one byte, and a vector<bool> packs eight flags into one byte. So it uses less memory, but it does not return a true reference to an element. Writing used[i] = true works as expected, so this detail rarely causes trouble. Be aware of it if you ever try to take the address of an element.

Version 2 touches only the string. Each swap moves two characters. A string is stored as one block of memory, so the swap is a read and a write of two bytes. The whole algorithm uses the same block the whole time, plus one frame per position.

The recursion depth is n in both versions, so the stack space is O(n). The total number of permutations is n factorial, which grows fast. For n equal to 10, there are 3,628,800 permutations, and each one takes time O(n) to print or copy. That is why the total work is O(n times n!).

Complexity

Let n be the number of items.

• The number of permutations of distinct items is n!. Each one has n positions.
• Generating and printing all of them takes O(n times n!) time.
• Counting them without printing still visits about n! leaves, so counting takes O(n!) time in the simple version. A better method can count faster when the rule allows it, but the simple version is the one to write in an interview unless asked otherwise.
• The recursion depth is n, so the extra space is O(n) in both versions, excluding the output.
• The next_permutation loop uses O(1) extra space beyond the array. Its time is O(n times n!) to visit every ordering.

Give the growth of n factorial a concrete feel. For n equal to 5 there are 120 orderings. For n equal to 8 there are 40,320. For n equal to 12 there are about 479 million, which is too many to print in any reasonable time. A program that needs every permutation of 12 items is asking for something that cannot finish.

Comparing the three versions

Each version has a place. This table puts them side by side.

The used-array version is the easiest to explain, because each loop pass is one choice. The swap version uses less memory, but its order is harder to predict, so check its output by tracing rather than by assuming. next_permutation is the shortest correct answer for real code, but an interviewer usually wants to see the recursion, so know both.

How next_permutation works, by hand

The standard algorithm behind next_permutation is short enough to trace on paper. It takes one ordering and produces the next one in dictionary order, with no recursion.

1. Find the largest index i where a[i] is less than a[i + 1]. If no such index exists, this is the last ordering.
2. Find the largest index j greater than i where a[j] is greater than a[i].
3. Swap a[i] and a[j].
4. Reverse everything after position i.

Start from 1 3 2. Step 1: a[0] is 1 and a[1] is 3, so i is 0, because a[1] is 3 and a[2] is 2, which is not an increase. Step 2: the largest j with a[j] greater than 1 is 2. Step 3: swap positions 0 and 2, which gives 2 3 1. Step 4: reverse positions 1 and 2, which holds 3 1, giving 2 1 3. The next ordering after 1 3 2 is 2 1 3, which matches the list printed by the program.

Try 2 3 1. Step 1: a[1] is 3 and a[2] is 1, which is not an increase, but a[0] is 2 and a[1] is 3, so i is 0. Step 2: j is 1, because a[1] is 3 and a[2] is 1 is not greater than 2. Step 3 gives 3 2 1. Step 4 reverses positions 1 and 2, which holds 2 1, giving 3 1 2. That matches the list.

Finally 3 2 1 has no increase from left to right at all, so step 1 finds no index, and the function returns false. That is why the loop in the program ends after the last ordering.

Because the method only ever changes the tail of the ordering, it uses O(1) extra memory and produces the orderings in order. It also handles repeated values, because the comparisons are strict: two equal values never count as an increase, so the same ordering is never produced twice.

How fast does n factorial grow?

The table below shows the number of orderings and a rough time to print each one at one million lines per second. The numbers make the case for counting instead of printing.

Each step up in n multiplies the count by n, so the growth is faster than any power of n. Interviewers use this table to test whether you can see when a list is too big to build. When the answer is a count, return the count. When it is a yes or no, stop at the first success.

Permutations with a fixed prefix

Many questions fix part of the answer. For example, a menu might require that the first course is always the soup, and the question asks for every order of the other courses. The method is the same, with a small change: put the fixed items into cur and mark them as used before the first call, then permute only the rest. The recursion now starts at the first free position, so its depth is the number of free items, not the total. Practise this change, because it appears in scheduling questions in many forms.

What interviewers listen for

When asked for all permutations, a clear answer covers four points. Name the pattern: each position takes one of the items not yet used. State the count before any code: n factorial. Describe the undo, which for the used-array version is two lines, the vector pop and the flag reset. Explain the duplicate rule and why it works, which is that equal values must be used left to right. Then give the complexity: time O(n times n!), because the output size dominates.

Ask a question before you start coding. Should the function print each permutation, return them in a list, or only count them? The answer changes the code, and asking shows that you think about the output as well as the method.

A trace table for the swap version

The swap version is harder to predict than the used-array version, so trace it in a table. Take abc. Each row is one leaf: the letters the loops placed at positions 0 and 1, and the string that permute prints when position 2 is filled.

Each row came from one pair of swaps, and each swap was undone before the next loop pass. The row for b at position 0 shows the pattern most clearly. The loop at position 0 reaches i equal to 1, which swaps a and b, so the string is bac. The recursion finishes with that string, and then the undo swaps a and b back to abc. The loop at position 0 can then try c next.

Read the table from top to bottom and the order matches the program's output. The table also shows that no row is missing. Position 0 takes each of the three letters, and position 1 takes each of the two letters that are left, so there are 3 times 2 equals 6 rows. That is the same count the tree gives, and it is easy to check at a glance.

Common mistakes and the messages you will see

Mistake 1: forgetting the undo. In version 1, leaving out used[i] = false makes later branches skip valid items. The output has fewer than n! lines. In version 2, leaving out the second swap leaves the string scrambled, so later branches print strings with letters in the wrong places. The fix is always the undo.

Mistake 2: starting the loop at 0 in the swap version. The loop must start at start. Starting at 0 moves a letter that the earlier calls already fixed, and the output has repeats and misses.

Mistake 3: forgetting to sort before next_permutation. The output is incomplete. No error is shown. Always sort first, unless you are sure the array is already at its smallest ordering.

Mistake 4: missing include. If you use sort or next_permutation without including <algorithm>, g++ stops with:

error: 'sort' was not declared in this scope; did you mean 'short'?

The fix is #include <algorithm> at the top of the file. The same message appears for next_permutation with its own name.

Mistake 5: duplicates in the output. If the input has repeated values and the code has no duplicate skip, the same arrangement is printed more than once. The output looks right at a glance, but the count is wrong. Count the lines, and compare the count with n factorial divided by the factorial of each repeat count. For {1, 1, 2} the answer is 3, not 6.

Mistake 6: sized vector without resize. If you write vector<int> a; and then a[i] = ... without resize, the program writes past the end of an empty vector. The result is undefined behavior, which may crash or print nonsense. Use resize or construct the vector with its size.

Debugging walkthrough

A student writes version 2 without the undo line and runs it on abc. The output is:

abc
acb
cab
cba
abc
acb

There are six lines, but the list is wrong. It repeats abc and acb, and it never shows bac or bca. The student adds a line to print the string on each return and sees that the swap at position 0 starts from acb, not from abc. The second swap, which should restore the string, is missing.

The buggy version looks like this:

void permute(string& s, int start) {
    if (start == (int)s.size()) { cout << s << "\n"; return; }
    for (int i = start; i < (int)s.size(); i++) {
        swap(s[start], s[i]);
        permute(s, start + 1);
        // bug: the undo swap is missing
    }
}

Without the undo, each later loop pass starts from a scrambled string. The fix is to add swap(s[start], s[i]); after the recursive call. The method is to print the string after each call and check that it is the same as the start of the call when the function returns. That property must hold for every backtracking function.

Variations and edge cases

Rotations. Some problems ask for circular arrangements, where two orderings that are rotations of each other count as the same. Fix the first item, then permute the rest. This reduces the count from n! to (n minus 1)!.

Partial permutations. Choose k items out of n and arrange them in order. The count is n times (n minus 1) and so on down to (n minus k plus 1). The recursion stops when the chosen list has k items, not n.

Next permutation in a loop. When the input is already sorted and you only need the ordering after a given one, next_permutation gives it in one call.

Empty input. An empty list has one permutation, the empty one. The base case handles this case if you check the size before the loop. Test it first.

Large inputs. Do not generate all permutations for n above about 10 unless the problem is about the answers themselves. Look for a counting or pruning method instead.

Interview questions

• How many permutations does a list of n distinct items have? Answer n factorial, with a short reason: n choices for the first position, n minus 1 for the second, and so on.
• Why does the duplicate skip need !used[i - 1]? Answer that it forces equal values to be used left to right, so each arrangement is produced once.
• What is the time complexity of generating all permutations? Answer O(n times n!), because there are n! of them and each takes O(n) to output.
• Why sort before next_permutation? Answer that it walks forward only, so it must start at the smallest ordering to see all of them.

Real-world uses

Permutations are behind several everyday features. A scheduling tool that tries orders of tasks to find the cheapest route is checking permutations, often with pruning to skip poor orders early. A puzzle game that checks whether letters can form a word searches arrangements of its tiles. A test system that runs checks in every order to find order-dependent failures generates permutations of its test list. A seating planner that checks each arrangement against rules is counting permutations with conditions, like the derangement example.

Practice

Write each exercise before you open the solution. The hints are there to help you start.

1. Write a recursive long long countPerms(int n) that returns n factorial without storing any list. Hint: n times the count for n minus 1. Check n equal to 0, 1, 4 and 6.

long long countPerms(int n) {
    if (n <= 1) return 1;
    return n * countPerms(n - 1);
}

2. Predict how many lines the version 1 program prints for {1, 1, 2, 2} without the duplicate skip. Then predict how many it prints with the skip.

3. Write a recursive function that prints every permutation of the characters in "ab", then extend it to "abcd" and count the lines. Predict the count before you run it.

4. Explain in one sentence why the loop in the swap version starts at start and not at 0.

5. Count the derangements of 3 by hand and check your answer with the program. Then count the derangements of 5 with the program, and predict whether the number is larger or smaller than the number for 4.

6. Write bool hasFixedPoint(const vector<int>& p, int i), called with 0 for i, that returns true when some position i has p[i] == i + 1, which means the value sits in its original place for 1-based values. Test with {2, 1, 3}, which has a fixed point at position 3.

bool hasFixedPoint(const vector<int>& p, int i) {
    if (i == (int)p.size()) return false;
    if (p[i] == i + 1) return true;
    return hasFixedPoint(p, i + 1);
}

7. A student writes sort but leaves out the #include <algorithm> line. Predict the message and explain the fix.

8. Write a loop-based version that prints every permutation of {1, 2, 3} in the order produced by next_permutation starting from the descending order 3 2 1. Predict whether it prints all six permutations, and explain.

9. Write void partial(int n, int k, vector<bool>& used, vector<int>& cur) that prints every arrangement of k distinct items chosen from 1 to n, with used and cur starting empty. Test with n equal to 4 and k equal to 2, which should print 12 lines.

void partial(int n, int k, vector<bool>& used, vector<int>& cur) {
    if ((int)cur.size() == k) {
        for (int x : cur) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (used[v - 1]) continue;
        used[v - 1] = true;
        cur.push_back(v);
        partial(n, k, used, cur);
        cur.pop_back();
        used[v - 1] = false;
    }
}

10. Explain why generating every permutation of 12 items is not practical, using the count and a rough speed. Assume a computer prints one million lines per second.

What you now know

• A permutation fills positions one at a time, and each position chooses from the items not yet used.
• A list of n distinct items has n factorial permutations, and the decision tree has n factorial leaves.
• A used array marks which items are placed. The swap version fixes positions in place and undoes each swap.
• With repeated values, sort first and skip a value when the one before it is not in use.
• next_permutation gives the orderings in order and handles duplicates, but it needs a sorted start.
• Count instead of printing when the question asks for a number, and add a rule on each position to skip invalid branches.