fn main() {
    let sequence:Vec<i32> = (1..5).collect();

    print_all_permutations(sequence);
}

fn print_all_permutations(mut sequence:Vec<i32>) {
    sequence.sort();

    println!("{:?}", sequence);

    while let Some(k) = largest_k(&sequence) {
        //println!("k is: {}", k);
        let l = largest_l(&sequence, k);
        //println!("l is: {}", l);
        swap(&mut sequence, k, l);
        let n = sequence.len();
        reverse_range(&mut sequence, k+1, n);
        println!("{:?}", sequence);
    }

}

fn largest_k(arr:&Vec<i32>) -> Option<usize> {
    let mut result = None;

    for k in 0..arr.len()-1 {
         if arr[k] < arr[k+1] {
             result = Some(k);
         }
    }

    result
}

fn largest_l(arr:&Vec<i32>, k:usize) -> usize {
    let mut result = 0;

    for l in k+1..arr.len() {
        if arr[k] < arr[l] && l > result {
            result = l;
        }
    }

    result
}

fn swap( arr: &mut Vec<i32>, one:usize, two:usize) {
    //println!("swapping {} and {} in {:?}", arr[one], arr[two], arr);
    let temp = arr[two];
    arr[two] = arr[one];
    arr[one] = temp;
    //println!("swapped: {:?}", arr);
}

fn reverse_range(arr: &mut Vec<i32> , range_start:usize, range_end:usize) {
    //println!("reversing from pos: {} to pos: {} in {:?}", range_start, range_end, arr);
    let mut rev = arr[range_start..range_end].to_vec();
    rev.reverse();

    //println!("reversed slice is: {:?}", rev);

    for (arr_i, rev_i) in (range_start..range_end).zip(0..arr.len()) {
        arr[arr_i] = rev[rev_i];
    }
}