Problem overview
The method generateValleyPermutations(_ n: Int) returns every valley permutation of the numbers 1 to n, as a [[Int]]. A valley permutation first decreases and then increases: it is a strictly decreasing run, followed by a strictly increasing run, and the lowest point of the valley is the value 1.
For n = 4 the answer has eight permutations: [1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [3, 2, 1, 4], [4, 1, 2, 3], [4, 2, 1, 3], [4, 3, 1, 2] and [4, 3, 2, 1]. A permutation such as [1, 4, 2, 3] is not a valley: it goes up to 4, down to 2 and up again, so it has a peak in the middle.
Approach: one bit per value decides its side
Trying all n! permutations and testing each would be hopelessly slow for n = 10. Look at the structure instead. The smallest value, 1, must sit at the bottom of the valley, because every neighbour of the bottom is larger. Every other value, 2 to n, is either to the left of 1 (in the decreasing part) or to the right (in the increasing part).
Once each value has chosen a side, the permutation is fixed: the left values are written in decreasing order, then 1, then the right values in increasing order. So a valley permutation is exactly one choice of side for each of the n - 1 values, which gives 2^(n - 1) permutations. For n = 4 that is 8, matching the list above.
A counter mask from 0 to 2^(n - 1) - 1 visits every combination of n - 1 bits exactly once. Bit i of the mask says where the value i + 2 goes: a set bit means left, a clear bit means right.
Step by step
- Create
resultas an empty[[Int]]withvar, because permutations will be appended to it. - Loop over every mask with
for mask in 0..<(1 << (n - 1)). The range..<excludes its upper bound, and1 << kis2^k, so this covers 0 up to2^(n - 1) - 1. - Start fresh lists
leftandrightinside the loop, both empty[Int]variables. Declaring them inside means each mask begins empty. - Loop over the bits with
ifrom 0 ton - 2. That isn - 1iterations, one per value from 2 ton. - Compute the value this bit controls:
let val = i + 2. The offset is 2 because value 1 needs no bit. - Test the bit.
(mask >> i) & 1 == 1shifts bitidown to the lowest position and keeps only it. If it is set, appendvaltoleft; otherwise append it toright. - Sort the two lists.
leftgoes in descending order so the prefix falls towards 1, andrightin ascending order so the suffix rises away from it. - Join and record.
left + [1] + rightbuilds the permutation, and it is appended toresult. - Return
resultafter the outer loop, once every mask has produced its permutation.
The solution in Swift
class Solution {
func generateValleyPermutations(_ n: Int) -> [[Int]] {
var result = [[Int]]()
for mask in 0..<(1 << (n - 1)) {
var left = [Int]()
var right = [Int]()
for i in 0..<(n - 1) {
let val = i + 2
if (mask >> i) & 1 == 1 {
left.append(val)
} else {
right.append(val)
}
}
left.sort(by: >)
right.sort()
let perm = left + [1] + right
result.append(perm)
}
return result
}
}
Swift details worth a closer look:
- Conditions must be
Bool. In some languagesif (mask >> i) & 1is enough, because a nonzero integer counts as true. Swift needs the explicit== 1, since anIntis not aBool. Precedence is also different from C: in Swift,&binds tighter than==, so the comparison applies to the masked bit. sortversussorted.left.sort(by: >)sorts the array in place, which is whyleftis avar. Passing the operator>as the comparison gives descending order.sortedwould return a new array instead.- Ranges.
0..<(n - 1)is a half-open range. A range whose upper bound is below its lower bound, such as0..<(-1), crashes at run time, so it matters that the code never builds one (see the edge cases). - Arrays are values.
left + [1] + rightcreates a new array. Appendingpermtoresultstores a copy, and the next iteration's freshleftandrightcan't change it. - Type inference.
[[Int]]()and[Int]()spell out the element types of the empty arrays.1 << (n - 1)is anInt, the same type asmask.
Complexity
Time: O(n * 2^n). There are 2^(n - 1) masks. For each, the inner loop runs n - 1 times, sorting the two lists costs O(n log n), and joining them costs O(n). That makes O(n log n) per mask, and O(n log n * 2^n) overall. The lists are built in increasing order, so the sorting work is small in practice, but this bound holds in general.
Space: O(n * 2^n). The result holds 2^(n - 1) permutations of length n. Apart from the result, only the two lists of at most n values are alive at once.
Edge cases and common mistakes
n = 1. The only mask is 0, the inner loop does nothing, and the result is[[1]].n = 2. Two permutations:[1, 2]and[2, 1].n = 0. The expression1 << (n - 1)is1 << -1. Swift's shift operators treat a negative shift amount as a shift the other way, so this evaluates to 0. The outer range0..<0is empty, the inner range is never built, and the method returns[].- Wrong order inside a side. If
leftis not sorted descending, the prefix won't be decreasing, and the output would contain non-valleys such as[2, 3, 1](hereleftheld 2 and 3 in ascending order). - Putting 1 in the wrong place. The 1 always goes between
leftandright. Any other position breaks the valley shape. - Reusing
leftandrightacross masks. If they were declared outside the outer loop, values from the previous mask would stay in them. - Using
0...(n - 1)for the bit loop. The range0...(n - 1)is inclusive and would visit one value too many,n + 1, which is not in the permutation.
Testing
n = 1gives[[1]].n = 2gives[[1, 2], [2, 1]].n = 3gives[[1, 2, 3], [2, 1, 3], [3, 1, 2], [3, 2, 1]].n = 4gives the eight permutations listed at the top.n = 10returns 512 permutations.
