今週のアルゴリズム：最短経路の計算！(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);
}