Start learning free

LESSON 315 OF 338 · DYNAMIC PROGRAMMING

Swap Permutations in Go: A Linear Recurrence with a Slice

Practice O(n) Read the full explanation

Given a non-negative integer N return the number of swap permutations of length N

A swap permutation is obtained from the identical permutation (1, 2, 3, ..., N) by applying the swap operation multiple times

A swap operation consists of picking two different items from the permutation and swapping them

You are allowed to swap an item at most once

Example:

Input: N = 3
Output: 4
Explanation: [
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [3, 2, 1]
]
We start from [1, 2, 3], which is a swap permutation
because we  applied 0 swap operations, and we apply
one of the following swaps:
[1, 2, 3] => [1, 3, 2]
[1, 2, 3] => [2, 1, 3]
[1, 2, 3] => [3, 2, 1]
Notice that we can only apply one swap operation
because we are left with only 1 item that is not swapped.
For larger values of N we can have multiple chained operations.
Notes: 3 <= N <= 12
STEP 1 OF 5
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Swap Permutations in Go, explained

    Problem overview

    The method countPermutations(n) returns how many permutations of length n can be reached from (1, 2, ..., n) by swapping pairs of items, where no item may be swapped more than once. Applying zero swaps is allowed, so the identity permutation counts.

    For n = 3 the answer is 4: the identity [1, 2, 3], plus the three single swaps [1, 3, 2], [2, 1, 3] and [3, 2, 1]. A second swap is impossible, because after one swap only one item is still untouched, and a swap needs two. For larger n several swaps can be chained as long as they use different items. The notes keep n between 3 and 12.

    Approach: decide what happens to the last item

    Because every item is swapped at most once, the final arrangement is made of disjoint pairs that traded places, and all other items stayed where they were. So the question is how many ways there are to pick such pairs among n items.

    Let dp[i] be the answer for i items and look at item i:

    • It is never swapped. It stays in place, and the other i - 1 items are arranged in dp[i-1] ways.
    • It is swapped with one of the other i - 1 items. There are i - 1 choices of partner. Both items are then used up, so the remaining i - 2 items are arranged in dp[i-2] ways.

    These two cases don't overlap, and together they cover every possibility, so dp[i] = dp[i-1] + (i-1) * dp[i-2]. The base cases are dp[1] = 1 (one item can only stay) and dp[2] = 2 (stay, or swap once).

    The values grow like this:

    n:      1  2  3   4   5   6
answer: 1  2  4  10  26  76

    Check n = 3: dp[3] = dp[2] + 2 * dp[1] = 2 + 2 = 4, matching the example. Check n = 4: dp[4] = 4 + 3 * 2 = 10.

    Step by step

    1. Create the slice dp with make([]int, n+1). It has one more cell than needed so that dp[i] is the answer for i items; cell 0 is unused.
    2. Set the base cases with a single tuple assignment: dp[1], dp[2] = 1, 2.
    3. Loop from 3 to n inclusive. Each value uses the two before it, which are already computed.
    4. Apply the recurrence to dp[i].
    5. Return dp[n].

    The solution in Go

    type Solution struct{}

func (Solution) countPermutations(n int) int {
	dp := make([]int, n+1)
	dp[1], dp[2] = 1, 2
	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + (i-1)*dp[i-2]
	}
	return dp[n]
}

    Go details worth a closer look:

    • The receiver has no name. (Solution) declares the method on the type without binding a variable, which is legal when the body doesn't use the receiver.
    • Tuple assignment. dp[1], dp[2] = 1, 2 evaluates the right side first and then assigns. The same form swaps two variables without a temporary: a, b = b, a.
    • make([]int, n+1) returns a slice of n + 1 zeros. Indexing past the end is not an overflow but a run-time panic.
    • Loop style. Go has only for. The three-part form here is the usual counting loop, and the variable i exists only inside it.
    • Integer size. int is 64 bits here. The answer for n = 12 is 140,152, and values stay well inside the range for much larger n. A silent wrap would only appear far beyond the lesson's limits.

    Complexity

    One loop of about n steps with constant work in each gives O(n) time. The slice holds n + 1 integers, so the space is O(n). Since each value needs only the previous two, two variables could replace the slice and bring the space down to O(1).

    Edge cases and common mistakes

    • n below 2. With n = 1 the slice has two cells, so dp[2] = 2 is out of range and the program panics. The lesson's notes start at n = 3, so this isn't tested, but a general-purpose version would return early for small n.
    • Forgetting the factor i - 1. Item i can pick any of i - 1 partners, so dp[i-1] + dp[i-2] would count only one of them. For n = 4 it would give 6 instead of 10.
    • Counting ordered sequences of swaps. Swapping (1, 2) and then (3, 4) gives the same permutation as the other order. The recurrence counts resulting permutations, not sequences of operations.
    • Confusing this with all permutations. For n = 4 there are 24 permutations but only 10 swap permutations. For example, the cycle [2, 3, 1, 4] is not reachable without moving an item twice.

    Testing

    The values for n from 3 to 6 are 4, 10, 26 and 76, and n = 12 gives 140152. These numbers also count the permutations that are their own inverse, which is a handy way to cross-check the idea.

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free