Generate Valley Permutations in Rust

Given a non-negative integer n, return all the valley permutations of length n.

A valley permutation is defined as a permutation that is a concatenation of two parts: a monotonically decreasing sequence and then a monotonically increasing sequence.

E.g. valley permutations follow this format: [p[0] < p[1] < p[2] < ... < p[k] > p[k+1] > p[k + 2] > ... > p[n]].

Example:

Input: n = 4

Output:[
    [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],
    [4, 3, 2, 1]
]

Explanation:
Permutations suchs as [1, 4, 2, 3] are not valley because 1 < 4 > 2 < 3

Notes: n <= 10