Problem overview
The method generateValleyPermutations takes an integer n and returns every permutation of the numbers 1 to n that forms a valley: a strictly decreasing run followed by a strictly increasing run. The result is a mutable.ArrayBuffer[Array[Int]], with n <= 10.
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, then down, then up again.
Approach: choose a side for every value
A valley has one lowest point, and the lowest of the numbers 1 to n is 1. So 1 always sits at the bottom, with a decreasing run on its left and an increasing run on its right (either run may be empty).
Once you know which values are on the left and which are on the right, the permutation is fixed. The left values must appear largest first, the right values smallest first. So each valley permutation is determined by one decision per value from 2 to n: left or right. That is n - 1 independent two-way choices, hence 2^(n - 1) valley permutations, and for n = 10 that is 512.
A bitmask represents such a set of choices neatly. Count a number mask from 0 up to 2^(n - 1) - 1. Every such number is a different combination of n - 1 bits, and bit i says which side the value i + 2 goes on. This avoids generating all n! permutations and filtering them, which for n = 10 would mean 3,628,800 candidates instead of 512.
Step by step
- Create
result, an emptymutable.ArrayBuffer[Array[Int]]. - Loop over the masks from 0 up to
(1 << (n - 1)) - 1. Shifting 1 left byn - 1places gives2^(n - 1), anduntilleaves that upper bound out. - Create fresh
leftandrightbuffers inside the loop, so nothing from the previous mask leaks in. - Loop
iover the bits,0 until n - 1. That is one iteration per value from 2 ton. - Compute
value = i + 2. The offset is 2 because 1 sits at the bottom and needs no bit. - Test bit
iwith((mask >> i) & 1) == 1. A set bit sends the value toleft, a clear bit toright. - Sort the halves:
leftin descending order andrightin ascending order, so they form the two sides of the valley. - Assemble the permutation in an
Array[Int]of sizen: copyleft, store 1, then copyright, advancing an index after each write. Append the array toresult. - Return
resultafter the outer loop has finished.
The solution in Scala
class Solution {
def generateValleyPermutations(n: Int): mutable.ArrayBuffer[Array[Int]] = {
val result = mutable.ArrayBuffer[Array[Int]]()
for (mask <- 0 until (1 << (n - 1))) {
val left = mutable.ArrayBuffer[Int]()
val right = mutable.ArrayBuffer[Int]()
for (i <- 0 until n - 1) {
val value = i + 2
if (((mask >> i) & 1) == 1) {
left += value
} else {
right += value
}
}
left.sortInPlaceWith(_ > _)
right.sortInPlaceWith(_ < _)
val perm = new Array[Int](n)
var idx = 0
for (v <- left) {
perm(idx) = v
idx += 1
}
perm(idx) = 1
idx += 1
for (v <- right) {
perm(idx) = v
idx += 1
}
result += perm
}
return result
}
}
The Scala details worth a closer look:
- Bit operators.
<<and>>shift anInt, and&keeps only the bits set in both operands.(mask >> i) & 1moves bitito the lowest position and masks everything else away, leaving 0 or 1. - The comparison is explicit and the parentheses matter. An
ifcondition must be aBoolean, so the 0 or 1 is compared with== 1. In Scala,==binds more tightly than&, so(mask >> i) & 1 == 1would be read as(mask >> i) & (1 == 1)and the compiler rejects it, because&on anIntcan't take aBoolean. untilexcludes its end.0 until n - 1gives0, 1, ..., n - 2. The arithmeticn - 1is evaluated beforeuntil, becauseuntilis an ordinary method with lower precedence than-.sortInPlaceWithsorts the buffer itself and takes a "comes before" function:_ > _puts larger values first,_ < _smaller values first. The values were added in increasing order, sorightis already sorted; the second sort just makes the intent explicit.- No
++in Scala. That is why each increment is its ownidx += 1statement. - Arrays inside the buffer. Each permutation is a fresh
Array[Int], so appending it doesn't alias an earlier one. Printing anArraydirectly shows something like[I@1a2b3c; usemkStringto print its contents.
Complexity
Let m = 2^(n - 1) be the number of permutations.
Time: O(2^n * n log n). Each of the m masks costs O(n) to split the values, up to O(n log n) to sort the two halves, and O(n) to assemble the array. Because the output has m * n numbers, any solution needs at least O(2^n * n).
Space: O(2^n * n) for the result itself, plus O(n) for the temporary buffers.
Edge cases and common mistakes
n = 1. The loop runs for masks 0 until1 << 0, which is just mask 0. Both halves stay empty and the result is[1].n = 2. The result is[2, 1]and[1, 2], one of each side for the value 2.n = 3. The result is[1, 2, 3],[2, 1, 3],[3, 1, 2]and[3, 2, 1].- Counting the bit for 1. Using
nbits instead ofn - 1would double the output with duplicates. Value 1 never needs a side. - Wrong sort direction. If
leftwere ascending, the permutation would rise and fall instead of forming a valley. - Reusing the buffers across masks. Declaring
leftandrightoutside the loop would carry values over from one mask to the next, andpermwould overflow its size.
Testing
n = 1gives[1].n = 2gives[1, 2]and[2, 1], in that order.n = 3gives[1, 2, 3],[2, 1, 3],[3, 1, 2],[3, 2, 1].n = 4gives the eight permutations listed in the overview, in that order.n = 10gives 512 permutations.
