今週のアルゴリズム：最短経路の計算！(Boo/C#/Nemerle/VBで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参照)

Boo

#!/usr/bin/booi
import System
import System.Array

def next_permutation[of T(IComparable)](a as (T),n as int) as bool:
	if n<0 or len(a)<n: return false
	Reverse(a,n,len(a)-n)
	i=len(a)-2
	while i>=0:
		if a[i].CompareTo(a[i+1])<0: break
		i-=1
	if i<0:
		Reverse(a)
		return false
	k=i
	i=len(a)-1
	while i>=0:
		if a[k].CompareTo(a[i]): break
		i-=1
	l=i
	z=a[k];a[k]=a[l];a[l]=z
	Reverse(a,k+1,len(a)-(k+1))
	return true

N=6
e0 as (int)=array(int,N*2)
f0 as (int)=array(int,N*2)
for i in range(N): e0[N+i]=f0[N+i]=1
Sort(e0)
Sort(f0)

r=0
i=0
e as (int)=array(int,N*2+1)
f as (int)=array(int,N*2+1)
while true:
	for i in range(N*2): e[i+1]=e[i]+e0[i]
	#数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。
	while true:
		x=1
		for i in range(N*2):
			f[i+1]=f[i]+f0[i]
			if e[i]==f[i] and e[i+1]==f[i+1]: x=0;break
		r+=x
		#i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。
		if not next_permutation[of int](f0,len(f0)): break
	if not next_permutation[of int](e0,len(e0)): break
print(r) # 100360

C#

using System;
using System.Collections.Generic;
class CodeIQRoute{
	static bool next_permutation<T>(List<T> a,int? _n=null) where T : IComparable<T>{
		int n=_n ?? a.Count;
		if(n<0||a.Count<n)return false;
		int i;
		a.Reverse(n,a.Count-n);
		for(i=a.Count-2;i>=0;i--)if(a[i].CompareTo(a[i+1])<0)break;
		if(i<0){
			a.Reverse(0,a.Count);
			return false;
		}
		int k=i;
		for(i=a.Count-1;i>=k+1;i--)if(a[k].CompareTo(a[i])<0)break;
		int l=i;
		T z=a[k];a[k]=a[l];a[l]=z;
		a.Reverse(k+1,a.Count-(k+1));
		return true;
	}

	const int N=6;
	public static void Main(){
		int r=0,i;
		List<int>e0=new List<int>(),f0=new List<int>();
		for(i=0;i<N;i++){e0.Add(0);f0.Add(0);}
		for(i=0;i<N;i++){e0.Add(1);f0.Add(1);}
		int[] e=new int[N*2+1];
		int[] f=new int[N*2+1];
		do{
			for(i=0;i<N*2;i++)e[i+1]=e[i]+e0[i];
			do{
				for(i=0;i<N*2;i++){
					f[i+1]=f[i]+f0[i];
					if(e[i]==f[i]&&e[i+1]==f[i+1])break;
				}
				if(i==N*2)r++;
			}while(next_permutation(f0));
		}while(next_permutation(e0));
		Console.WriteLine(r);
	}
}

Nemerle

using System;
using System.Array;
using Nemerle.Imperative;

public class CodeIQRoute{
	static next_permutation[T](a:array[T],n:int):bool where T : IComparable[T]{
		when(n<0||a.Length<n)return false;
		mutable i:int=0;
		Reverse(a,n,a.Length-n);
		for(i=a.Length-2;i>=0;i--)when(a[i].CompareTo(a[i+1])<0)break;
		when(i<0){
			Reverse(a,0,a.Length);
			return false;
		}
		def k:int=i;
		for(i=a.Length-1;i>=k+1;i--)when(a[k].CompareTo(a[i])<0)break;
		def l:int=i;
		def z=a[k];a[k]=a[l];a[l]=z;
		Reverse(a,k+1,a.Length-(k+1));
		return true;
	}

	public static Main(): void{
		def N=6;
		mutable r:int=0;
		mutable i:int;
		def e0=array(N*2);
		def f0=array(N*2);
		for(i=0;i<N;i++){
			e0[i]=0;f0[i]=0;
			e0[N+i]=1;f0[N+i]=1;
		}
		Sort(e0);
		Sort(f0);
		def e=array(N*2+1);
		def f=array(N*2+1);
		for(i=0;i<N*2+1;i++){e[i]=0;f[i]=0;}
		do{
			for(i=0;i<N*2;i++)e[i+1]=e[i]+e0[i];
			do{
				for(i=0;i<N*2;i++){
					f[i+1]=f[i]+f0[i];
					when(e[i]==f[i]&&e[i+1]==f[i+1])break;
				}
				when(i==N*2)r++;
			}while(next_permutation(f0,f0.Length));
		}while(next_permutation(e0,e0.Length));
		Console.WriteLine(r);
	}
}

VB.Net

imports System
imports System.Collections.Generic
module CodeIQRoute
	function next_permutation(of T as IComparable(of T))(ByRef a as List(of T),optional ByVal _n as integer?=Nothing) as boolean
		dim n as integer=if(_n.HasValue,_n,a.Count)
		if n<0 orelse a.Count<n
			return false
		end if
		dim i as integer
		a.Reverse(n,a.Count-n)
		for i=a.Count-2 to 0 step -1
			if a(i).CompareTo(a(i+1))<0
				exit for
			end if
		next
		if i<0
			a.Reverse(0,a.Count)
			return false
		end if
		dim k as integer=i
		for i=a.Count-1 to k+1 step -1
			if a(k).CompareTo(a(i))<0
				exit for
			end if
		next
		dim l as integer=i
		dim z as T=a(k):a(k)=a(l):a(l)=z
		a.Reverse(k+1,a.Count-(k+1))
		return true
	end function

	const N=6
	sub Main(ByVal args() as String)
		dim r,i as integer
		dim e0 as List(of integer)=new List(of integer)()
		dim f0 as List(of integer)=new List(of integer)()
		for i=0 to N-1
			e0.Add(0)
			f0.Add(0)
		next
		for i=0 to N-1
			e0.Add(1)
			f0.Add(1)
		next
		e0.Sort()
		f0.Sort()
		dim e as integer()=new integer(N*2){}
		dim f as integer()=new integer(N*2){}
		do
			for i=0 to N*2-1
				e(i+1)=e(i)+e0(i)
			next
			do
				for i=0 to N*2-1
					f(i+1)=f(i)+f0(i)
					if e(i)=f(i) andalso e(i+1)=f(i+1)
						exit for
					end if
				next
				if i=N*2
					r+=1
				end if
			loop while next_permutation(f0)
		loop while next_permutation(e0)
		Console.WriteLine(r)
	end sub
end module