Problem overview
The method generateValleyPermutations receives n and returns every valley permutation of the numbers 1 to n as a [][]int. A valley permutation goes down and then goes up: a strictly decreasing run, the minimum, and then a strictly increasing run. Either run may be empty, so [1, 2, 3, 4] (nothing before the 1) and [4, 3, 2, 1] (nothing after it) both count.
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]. The permutation [1, 4, 2, 3] is not a valley, because it rises, falls and rises again.
Approach: every value chooses a side
Trying all n! permutations and testing each one would work for small n, but the valley shape allows a direct construction. In a valley, the smallest value, 1, must be the bottom. Everything to its left is larger and decreasing toward it, and everything to its right is larger and increasing away from it.
So choose a side for each of the other values 2 to n. Once the values on the left are chosen, their order is forced (descending), and the same holds for the right (ascending). Each choice of sides gives exactly one valley, and different choices give different permutations. With n - 1 values and two sides each, there are 2^(n-1) valleys: 8 for n = 4, matching the example.
A bitmask enumerates the choices. Count mask from 0 to 2^(n-1) - 1; bit i of the mask says where value i + 2 goes: a set bit means left, a clear bit means right. For n = 4, the mask 101 in binary puts the values 2 and 4 on the left and 3 on the right, which gives [4 2 1 3].
Step by step
- Create
resultas an empty[][]int. - Loop over masks from 0 up to but not including
1 << (n - 1), which is 2^(n-1). Every combination ofn - 1bits appears exactly once. - Start fresh lists. Inside the loop, declare empty
leftandrightslices, so nothing carries over from the previous mask. - Visit the values. An inner loop runs
ifrom 0 ton - 2, andval := i + 2is the value that biticontrols. - Test the bit and place the value.
(mask>>i)&1 == 1moves bitito the lowest position and keeps only it. Appendvaltoleftif the bit is set, otherwise toright. - Order the two sides:
leftdescending,rightascending. - Assemble the permutation: a copy of
left, then 1, then the values ofright. Append it toresult. - Return
resultafter the outer loop ends.
The solution in Go
The code uses the sort package, so the file needs this import:
import "sort"
type Solution struct{}
func (this Solution) generateValleyPermutations(n int) [][]int {
result := [][]int{}
for mask := 0; mask < (1 << (n - 1)); mask++ {
left := []int{}
right := []int{}
for i := 0; i < n-1; i++ {
val := i + 2
if (mask>>i)&1 == 1 {
left = append(left, val)
} else {
right = append(right, val)
}
}
sort.Sort(sort.Reverse(sort.IntSlice(left)))
sort.Ints(right)
perm := append([]int{}, left...)
perm = append(perm, 1)
for _, v := range right {
perm = append(perm, v)
}
result = append(result, perm)
}
return result
}
The Go details worth knowing:
- Shifts and precedence. In Go,
&and>>bind tighter than==, so(mask>>i)&1 == 1means((mask>>i)&1) == 1. The comparison with 1 is required: anifcondition must be abool, and Go never treats the integer 1 as true. - Descending sort.
sort.Intssorts ascending only. For descending order,sort.IntSlice(left)turns the slice into a sortable type,sort.Reverseflips its comparison, andsort.Sortruns the sort in place. - Copying with append.
append([]int{}, left...)copies the elements ofleftinto a new slice. Writingperm := leftwould share the same array, and appending 1 could overwrite memory that belongs toleft. Each stored permutation needs its own storage, becauseresultkeeps all of them. - Reassigning append.
appendmay return a slice backed by a new array, so its result is always assigned back:left = append(left, val). - The receiver. The method has a value receiver on an empty struct, so it needs no state. Call it as
Solution{}.generateValleyPermutations(4). - A negative shift count panics.
1 << (n - 1)withn = 0shifts by -1, which stops the program with a run-time error. Forn = 1the shift is 0, the loop runs once withmask = 0, and the result is[[1]].
Complexity
There are 2^(n-1) masks. For each one, the inner loop does n - 1 steps and the two sorts cost up to O(n log n), and the permutation takes O(n) to build. The total time is O(2^n * n log n). Because the values are visited in increasing order, right and the reverse of left are already sorted, so the sorts only restate the required order; dropping them would lower the cost to O(2^n * n), which is also the size of the output.
Space: the output holds 2^(n-1) permutations of length n, which for n = 10 is 512 permutations. Beyond the output, each iteration uses O(n) temporary space.
Edge cases and common mistakes
- n = 1. The only valley is
[1]. - n = 0. The shift panics. The mask approach needs
n >= 1, so a defensive version would return early for smaller values. - Putting 1 anywhere else. Any other position makes the permutation fail the valley shape, because the minimum must be the bottom of the valley.
- Forgetting the sorts or reversing them. Values on the left must decrease toward 1 and values on the right must increase away from it. A left side in ascending order produces a hill next to the 1.
- Sharing storage. Reusing one slice across masks, or building
permwithout a copy, makes stored permutations change after they were appended. - Off-by-one in the bit loop. There are
n - 1bits, one for each of the values 2 ton. The loop bound isi < n-1, and the value isi + 2.
Testing
generateValleyPermutations(1)gives[[1]].generateValleyPermutations(4)gives the eight permutations from the example, in the same order.len(generateValleyPermutations(10))is512.