Problem overview
The function generate_valley_permutations takes n and returns every valley permutation of the numbers 1 to n. A valley permutation first goes down and then goes up, like the shape of a valley: a decreasing run, the smallest value 1 at the bottom, and then an increasing run. Either run may be empty.
For n = 4 there are eight: 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: it goes up, down and up again. The function returns each permutation as a String in which every number is followed by a space, such as "2 1 3 4 ".
Approach: choose a side for each value
Searching all n! permutations and testing each is wasteful. A valley has so much structure that its shape is determined by a much smaller choice.
The value 1 is the smallest, so it is the bottom of the valley: the values before it decrease towards it and the values after it increase away from it. Each of the other values, 2 to n, then goes either to the left of 1, in the decreasing part, or to the right, in the increasing part. Once the sides are chosen, the order inside each side is forced: the left values in descending order, the right values in ascending order. So there are exactly 2^(n-1) valley permutations, one per way of assigning n - 1 values to two sides.
A bitmask encodes such an assignment. The numbers 0 to 2^(n-1) - 1 cover every combination of n - 1 bits. Bit i says which side value i + 2 goes to: set means left, clear means right.
Step by step
- Create
resultas an empty mutable vector. - Loop over the masks from 0 up to but not including
1 << (n - 1), which is2^(n-1). The literal is written1i32so the shift has the same type asn. - Start two empty vectors,
leftandright, inside the loop so each mask begins fresh. - Loop over the bits with
ifrom 0 ton - 2. That is one iteration for each of the values 2 ton. - Compute the value that bit stands for:
val = i + 2. - Test the bit with
(mask >> i) & 1 == 1. If it is set, pushvalontoleft; otherwise ontoright. - Order the sides. Sort
leftin descending order andrightin ascending order. - Assemble the permutation: move
leftintoperm, push 1, then push the values ofright. - Convert it to text by formatting each number followed by a space and collecting the pieces into one
String, then push that intoresult. - Return
resultas the final expression.
The solution in Rust
impl Solution {
fn generate_valley_permutations(n: i32) -> Vec<String> {
let mut result = Vec::new();
for mask in 0..(1i32 << (n - 1)) {
let mut left: Vec<i32> = Vec::new();
let mut right: Vec<i32> = Vec::new();
for i in 0..(n - 1) {
let val = i + 2;
if (mask >> i) & 1 == 1 {
left.push(val);
} else {
right.push(val);
}
}
left.sort_by(|a, b| b.cmp(a));
right.sort();
let mut perm = left;
perm.push(1);
for v in right {
perm.push(v);
}
let s: String = perm.iter().map(|x| format!("{} ", x)).collect();
result.push(s);
}
result
}
}
The Rust details worth a closer look:
- Operator precedence. In Rust,
&binds tighter than==, so(mask >> i) & 1 == 1means((mask >> i) & 1) == 1. Anifcondition must be abool, which is why the explicit comparison is needed:if (mask >> i) & 1would be a type error. - Integer types.
maskandiare bothi32, liken. The range0..(n - 1)and the shiftmask >> ithen need no casts, and the sameiis used ini + 2to get the value. - Descending sort.
sort()orders ascending.sort_by(|a, b| b.cmp(a))compares with the arguments swapped, which reverses the order. Both vectors are filled in increasing order of value, so the explicitright.sort()doesn't change anything, but it states the intent. - Moving instead of copying.
let mut perm = left;moves the vector, andfor v in rightconsumesright, handing eachvover by value. Neither vector is used again, so nothing needs cloning. - Building the string.
perm.iter().map(|x| format!("{} ", x)).collect()produces one smallStringper number, andcollectjoins them because the target type is annotated asString. The result always ends with a space.
Complexity
Time. There are 2^(n-1) masks. For each one the code makes n - 1 bit tests, sorts two small vectors and builds a string of length proportional to n. The total is about O(2^n * n log n). With n at most 10, that's 512 permutations.
Space. The output holds 2^(n-1) strings of length proportional to n, so O(n * 2^n). Apart from it, each iteration uses only a few vectors of size n.
Edge cases and common mistakes
n = 1. The only mask is 0, both sides are empty and the answer is["1 "].n = 2. The answer is["1 2 ", "2 1 "].- The number 1 can't go anywhere else. It always sits where the decreasing part ends and the increasing part begins.
- Forgetting to sort the left side. Values are pushed in increasing order, so
leftwould be ascending, and a result such as2 3 1 4would rise before it falls, which is not a valley. - Counting up to the wrong limit. The masks must stop before
1 << (n - 1). Counting to1 << nwould produce each permutation twice, because the extra bit would have no value to control. n = 0. The shift amountn - 1is then -1, which is not a valid shift. In the optimized builds the lessons use, the shift amount wraps and the loop range ends up empty, so the function returns an empty vector. A debug build would panic with an overflow. The valid inputs start at 1.
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 eight strings, from"1 2 3 4 "to"4 3 2 1 ".n = 10gives 512 strings.
