impl Solution {
    pub fn get_permutation(n: i32, k: i32) -> String {
        let mut str_vec: Vec<i32> = (1..=n).collect();
        for i in 0..k-1 {
            Solution::next_permutation(&mut str_vec);
        }
        let a: Vec<String> = str_vec.iter().map(|item| item.to_string()).collect();
        return a.join("");
    }

    pub fn next_permutation(nums: &mut Vec<i32>) {
        // 从右向左找第一个升序对[i,i+1]
        if let Some(i) = nums[..nums.len() - 1].iter().enumerate()
            .rposition(|(pos, _)| nums[pos] < nums[pos + 1]) {
            // 从右向左找第一个比 nums[i] 大的数 nums[x]
            if let Some(x) = nums[(i + 1)..].iter().rposition(|item| item > &nums[i]) {
                nums.swap(i, i + 1 + x);
            }
            &nums[i + 1..].reverse();
        } else {
            nums.reverse();
        }
    }
}