Problem overview
The function generateValleyPermutations takes a non-negative integer n and returns every valley permutation of the numbers 1 to n. A valley permutation first decreases and then increases: it walks down to a lowest point and climbs back up. The result is a MutableList<IntArray>, one array per permutation.
For n = 4 there are eight valleys: [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 rises, falls and rises again.
Approach: the smallest value sits at the bottom
The obvious plan is to generate all n! permutations and keep the valleys. That works for tiny inputs and wastes almost all of its effort, since only a few permutations pass the filter. A better plan builds only valleys.
The key observation is that the lowest point of the valley must be the value 1. Every other value, 2 to n, then lies either on the descending side to the left of 1 or on the ascending side to the right. Once you decide the side of each value, the permutation is fixed: the left values must appear in decreasing order and the right values in increasing order, so there is no further freedom. With n - 1 values and two sides each, there are exactly 2^(n - 1) valleys. For n = 4 that is 8, matching the list above.
A binary number with n - 1 bits can record all these choices. Counting mask from 0 to 2^(n - 1) - 1 visits every combination of bits once. Bit i of the mask is the side of the value i + 2: 1 means left, 0 means right. For n = 3 the masks give [1, 2, 3] for 0, [2, 1, 3] for 1, [3, 1, 2] for 2 and [3, 2, 1] for 3.
Step by step
- Create the result list. It starts empty and collects one
IntArrayper mask. - Loop over all masks from 0 up to
(1 shl (n - 1)) - 1. Shifting 1 left bykplaces gives2^k, so this is every combination ofn - 1bits. - Make fresh
leftandrightlists inside that loop. Declaring them there gives each mask empty lists, so nothing leaks from the previous mask. - Loop over the bits with
ifrom 0 ton - 2. That isn - 1bits, one for each of the values 2 ton. - Compute the value this bit controls:
i + 2. Value 1 needs no bit because it always sits at the bottom. The variable is namedvalueand notvalbecausevalis a Kotlin keyword. - Send the value to a side. If bit
iis set, it goes toleft; otherwise toright. - Sort the sides.
leftmust decrease toward 1 andrightmust increase away from it. - Assemble the permutation. Fill an
IntArrayof sizenwith the left values, then 1, then the right values, tracking the next free position inidx. Add the array toresult. - Return
resultafter the outer loop, once every mask has produced its permutation.
The solution in Kotlin
class Solution {
fun generateValleyPermutations(n: Int): MutableList<IntArray> {
val result = mutableListOf<IntArray>()
for (mask in 0 until (1 shl (n - 1))) {
val left = mutableListOf<Int>()
val right = mutableListOf<Int>()
for (i in 0 until n - 1) {
val value = i + 2
if ((mask shr i) and 1 == 1) {
left.add(value)
} else {
right.add(value)
}
}
left.sortDescending()
right.sort()
val perm = IntArray(n)
var idx = 0
for (v in left) {
perm[idx++] = v
}
perm[idx++] = 1
for (v in right) {
perm[idx++] = v
}
result.add(perm)
}
return result
}
}
The Kotlin details worth a closer look:
- Bit operations are named functions. Kotlin has no
<<,>>or&operators for integers. It uses the infix functionsshl,shrandandinstead. - Precedence. Named infix functions bind tighter than
==, so(mask shr i) and 1 == 1means((mask shr i) and 1) == 1: shift bitito the lowest position, keep only it, and compare with 1. The comparison has to be written out, because anifcondition must be aBoolean; anIntsuch as 1 is not accepted as true. untilexcludes its upper bound.0 until n - 1covers 0 ton - 2. The range0..n - 1would includen - 1and read one bit too many.- In-place sorting. On a
MutableList,sort()andsortDescending()reorder the list itself and returnUnit. Since the values were added in increasing order,rightis already ascending andleftis ascending too, so onlyleftreally needs reversing. Both calls make the intent explicit. perm[idx++] = vstores at the current position and then movesidxforward by one.idxis avar; the lists arevalreferences to mutable lists, soaddstill works.IntArrayversusList<Int>.IntArray(n)is a primitive array filled with zeros, fixed in size. The lists hold boxedIntvalues and grow as needed, which suits collecting the sides before their sizes are known.
Complexity
Time: O(2^n * n log n). There are 2^(n - 1) masks. Each one loops over n - 1 bits, sorts lists of at most n - 1 values and copies n values into an array. The output itself holds n numbers per permutation, so no algorithm can do better than O(n * 2^n).
Space: O(n * 2^n). The result holds 2^(n - 1) arrays of n values. Apart from the output, the working lists need O(n). With n at most 10, that is 512 arrays of 10 numbers.
Edge cases and common mistakes
n = 1. The loop runs for the single mask 0, nothing goes to either side, and the result is[[1]].n = 2. The two valleys are[1, 2]and[2, 1]; both sequences have one of the two parts empty, which is allowed.n = 0.1 shl (n - 1)becomes1 shl -1, and Kotlin uses only the low five bits of the shift distance, so this is1 shl 31, a negative number. The loop range0 untilthat number is empty, so the function returns an empty list.- Reusing the side lists. Declaring
leftandrightoutside the mask loop would mix values from different masks. - Forgetting the descending order. Without sorting the left side in decreasing order, the permutation would rise before 1 instead of falling to it, and it would not be a valley.
- Reading the wrong bit count. Looping
iton - 1adds a valuen + 1that does not belong in the permutation, andpermoverflows.
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 arrays listed at the top, in that order.n = 5gives 16 permutations.