今週のアルゴリズム：最短経路の計算！(V/Rustでnext_permutation)

Permutation Iterator	next_permutation	URL
C#/Go/Python/Ruby/VB		まとめ含む http://qiita.com/cielavenir/items/ac96da5e3040c2edb78c
	Boo/C#/Nemerle/VB	http://qiita.com/cielavenir/items/0e07a024049017f7dea2
	Java/Groovy/Scala/Fortran/Pascal	http://qiita.com/cielavenir/items/4347fd0c6c69fa60804a
	D/Go/JavaScript/Lua/R	http://qiita.com/cielavenir/items/9e821d04f574a6623d03
Perl	HSP/PHP/Python/Ruby	http://qiita.com/cielavenir/items/006a878292c5be209231
Go2/Crystal/Kotlin/Nim/Julia		http://qiita.com/cielavenir/items/74f8d547437154c14e72
	V/Rust	http://qiita.com/cielavenir/items/cec1812999547909a9e4
D/Nemerle/JavaScript/Perl6/PHP	C/C++/Crystal/Go2/Julia Kotlin/Nim/Perl/Perl6	(github参照)

V

f<T>()からg<T>()を呼ぼうとするとコンパイル中に内部エラーが起きる。あと、rangeがないのでiter版は実装できないっぽい。

tyama_codeiq608_next.v

//usr/bin/env v run $0 $@;exit

//iter version cannot be implemented as "range ch" is missing.

fn reverse<T>(mut a []T,start_ int,size int){
    mut start:=start_
    for end:=start+size-1;start<end;start++ {
        z:=a[start]
        a[start]=a[end]
        a[end]=z
        end--
    }
}

fn next_permutation<T>(mut a []T, n int) bool{
    if n<0||a.len<n {return false}
    // "int" cannot be "T": https://github.com/vlang/v/issues/6222
    reverse<int>(mut a,n,a.len-n)
    mut i:=0
    for i=a.len-2;i>=0;i-- {if a[i]<a[i+1] {break}}
    if i<0 {
        reverse<T>(mut a,0,a.len)
        return false
    }
    k:=i
    for i=a.len-1;i>=k+1;i-- {if a[k]<a[i] {break}}
    l:=i
    z:=a[k]
    a[k]=a[l]
    a[l]=z
    reverse<T>(mut a,k+1,a.len-(k+1))
    return true
}

fn main(){
    n:=6
    mut e0:=[0].repeat(n*2)
    mut f0:=[0].repeat(n*2)
    mut i:=0
    mut r:=0
    for i=0;i<n;i++ {
        e0[n+i]=1
        f0[n+i]=1
    }
    e0.sort()
    f0.sort()
    for {
        for {
            mut flg:=0
            mut zero1:=0
            mut zero2:=n
            mut one1:=0
            mut one2:=n
            for i=0;i<n*2;i++ {
                if e0[i]==0 {zero1 ++}
                if e0[i]==1 {one1  ++}
                if f0[i]==0 {zero2 --}
                if f0[i]==1 {one2  --}
                if zero1==zero2 {flg++}
                if one1==one2 {flg++}
            }
            if flg>=2 {r++}
            if !next_permutation<int>(mut f0,f0.len) {break}
        }
        if !next_permutation<int>(mut e0,e0.len) {break}
    }
    println(r)
}

Rust

要素スワップは https://qiita.com/tanakh/items/d70561f038a0ef4f0ff1 を利用.

tyama_codeiq608_next.rs

fn reverse<T>(a:&mut[T],start_:usize,size:usize){
    let mut start=start_;
    let mut end=start+size-1;
    while start<end {
        {
            let p1: *mut T = &mut a[start];
            let p2: *mut T = &mut a[end];
            unsafe {p1.swap(p2);}
        }
        end-=1;
        start+=1;
    }
}

fn next_permutation<T: std::cmp::PartialOrd>(a:&mut[T],n:usize)->bool{
    if n<0||a.len()<n {return false}
    reverse(a,n,a.len()-n);
    let mut i=a.len()-2;
    loop {
        if a[i]<a[i+1] {break}
        if i==0 {
            reverse(a,0,a.len());
            return false;
        }
        i-=1;
    }
    let k=i;
    i=a.len()-1;
    while i>=k+1 {
        if a[k]<a[i] {break}
        i-=1;
    }
    let l=i;
    {
        let p1: *mut T = &mut a[k];
        let p2: *mut T = &mut a[l];
        unsafe {p1.swap(p2);}
    }
    reverse(a,k+1,a.len()-(k+1));
    return true;
}

fn main(){
    let N=6;
    let mut e0=vec![0 as i64; N*2];
    let mut f0=vec![0 as i64; N*2];
    let mut i=0;
    let mut r=0;
    while i<N {
        e0[N+i]=1;
        f0[N+i]=1;
        i+=1;
    }
    e0.sort();
    f0.sort();
    let mut e=vec![0 as i64; N*2+1];
    let mut f=vec![0 as i64; N*2+1];
    loop {
        i=0;
        while i<N*2 {
            e[i+1]=e[i]+e0[i];
            i+=1;
        }
        loop {
            i=0;
            while i<N*2 {
                f[i+1]=f[i]+f0[i];
                if e[i]==f[i]&&e[i+1]==f[i+1] {break}
                i+=1;
            }
            if i==N*2 {r+=1;}
            if !next_permutation::<i64>(&mut f0,N*2) {break}
        }
        if !next_permutation::<i64>(&mut e0,N*2) {break}
    }
    println!("{}",r);
}