Rust implementaion for next_permutation

next_permutation.rs

use std;
import core::option::{some, none};
import core::option;

fn next_permutation<T: copy>(v : [T]) -> option<[T]> {
  let n = vec::len(v) as int;
  let nv = vec::to_mut(v);
  if n < 2 {
    ret none;
  }
  let i = n - 1;
  while i > 0{
    i -= 1;
    if nv[i] < nv[i+1] {
      let j = n - 1;
      while nv[i] >= nv[j] {
        j -= 1;
      }
      vec::swap(nv, i as uint, j as uint);
      
      // i+1~nまでswapする
      let low = i + 1;
      let high = n - 1;
      while low < high {
        vec::swap(nv, low as uint, high as uint);
        low += 1;
        high -= 1;
      }
      ret some(vec::from_mut(nv));
    }
  }
  ret none;
}

fn permutation<T: copy>(v: [T], f: fn([T])) {
  f(v);
  let nv = next_permutation(v);
  while !option::is_none(nv) {
    let mv = option::get(nv);
    f(mv);
    nv = next_permutation(mv);
  }
}

#[cfg(test)]
mod test{
  fn match_next<T: copy>(orig: [T], expect: option<[T]>) {
    let actual = next_permutation(orig);
    assert actual == expect;
  }

  fn match_perm<T: copy>(orig: [T], expect: [[T]]) {
    let actual : [[T]] = [];
    permutation(orig) { |v|
      // log(info, v);
      actual += [v];
    }
    log(info, (expect, actual));
    assert(expect == actual);
  }
  
  #[test]
  fn test_next_perm1(){
    match_next([1, 2, 3], some([1, 3, 2]));
    match_next([1, 3, 2], some([2, 1, 3]));
    match_next([3, 1, 2], some([3, 2, 1]));
    match_next([3, 2, 1], none);
  }

  #[test]
  fn test_next_perm2(){
    match_next(['a', 'b', 'c'], some(['a', 'c', 'b']));
    match_next(['c', 'a', 'b'], some(['c', 'b', 'a']));
    match_next(['c', 'b', 'a'], none);
  }

  #[test]
  fn test_simple_number(){
    match_perm([1, 2, 3], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]);
  }
  
  #[test]
  fn test_simple_char(){
    match_perm(['A', 'B', 'C'], [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B'], ['C', 'B', 'A']]);
  }
  
}