今週のアルゴリズム：最短経路の計算！(Java/Groovy/Scala/Fortran/Pascalで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参照)

Java
ジェネリクスの使い方で苦労してます…。

import java.util.*;
class Main{
	static <T> void reverse(List<T> a,int start,int size){
		int end=start+size-1;
		for(;start<end;start++){
			T z=a.get(start);a.set(start,a.get(end));a.set(end,z);
			end--;
		}
	}
	static <T extends Comparable<? super T>> boolean next_permutation(List<T> a,int n){
		if(n<0||a.size()<n)return false;
		int i;
		reverse(a,n,a.size()-n);
		for(i=a.size()-2;i>=0;i--)if(a.get(i).compareTo(a.get(i+1))<0)break;
		if(i<0){
			reverse(a,0,a.size());
			return false;
		}
		int k=i;
		for(i=a.size()-1;i>=k+1;i--)if(a.get(k).compareTo(a.get(i))<0)break;
		int l=i;
		T z=a.get(k);a.set(k,a.get(l));a.set(l,z);
		reverse(a,k+1,a.size()-(k+1));
		return true;
	}
	static <T extends Comparable<? super T>> boolean next_permutation(List<T> a){
		return next_permutation(a,a.size());
	}

	static final int N=6;
	public static void main(String[]z){
		int r=0,i;
		List<Integer>e0=new ArrayList<Integer>(),f0=new ArrayList<Integer>();
		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.get(i);
			do{
				for(i=0;i<N*2;i++){
					f[i+1]=f[i]+f0.get(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));
		System.out.println(r);
	}
}

Groovy
Enumeratorの概念がないだけでこんなに汚くなるのね…。
※精査したところ、1行目だけ#コメントが許容されるようですが、記述した場合シンタックスハイライトがうまく動かなくなるようです。なので、コードブロックからは削除しました。chmod +xしたい場合は1行目に
#!/usr/bin/env groovy
を別途入れて下さい。

def next_permutation(a,n=a.size){
	if(n<0||a.size<n)return false
	if(n<a.size)a[0..a.size()-1]=a[0..n-1]+a[n..-1].reverse()
	k=(a.size-2..0).find{a[it]<a[it+1]}
	if(k==null){
		a[0..a.size()-1]=a.reverse()
		return false
	}
	l=(a.size()-1..k+1).find{a[k]<a[it]}
	z=a[k];a[k]=a[l];a[l]=z
	a[0..a.size()-1]=a[0..k]+a[k+1..-1].reverse()
	return true
}

N=6
e0=([0]*N+[1]*N).sort()
f0=([0]*N+[1]*N).sort()
//各Pは経路を表す。1が縦、0が横を表す。
r=0
i=0
e=[0]*(N*2+1)
f=[0]*(N*2+1)
while(true){
	(N*2).times{e[it+1]=e[it]+e0[it]}
	//数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。
	while(true){
		x=!(0..N*2-1).any{
			f[it+1]=f[it]+f0[it]
			//i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。
			e[it]==f[it] && e[it+1]==f[it+1]
		}
		if(x)r++
		if(!next_permutation(f0))break;
	}
	if(!next_permutation(e0))break
}
println r // 100360

Scala
chmod +xしたい場合は1行目に
#!/usr/bin/env scala
!#
を入れればよいですが、そうするとscalacでエラーになるので、コードブロックではやっておりません。

import scala.util.control.Breaks
object Main{
	def reverse[T](a: Array[T],start: Int,size: Int) = {
		val end=start+size-1
		for(i <- 0 to size/2-1){
			val z=a(start+i)
			a(start+i)=a(end-i)
			a(end-i)=z
		}
	}
	def next_permutation[T <% Ordered[T]](a: Array[T],n: Int): Boolean = {
		if(n<0||a.size<n)return false
		reverse(a,n,a.size-n)
		var k = -1
		val b = new Breaks
		b.breakable{
			for(i<-(a.size-2) to 0 by -1)if(a(i)<a(i+1)){k=i;b.break}
		}
		if(k<0){
			reverse(a,0,a.size)
			return false
		}
		var l = -1
		b.breakable{
			for(i<-a.size-1 to k+1 by -1)if(a(k).compare(a(i))<0){l=i;b.break}
		}
		val z=a(k);a(k)=a(l);a(l)=z
		reverse(a,k+1,a.size-(k+1))
		return true
	}
	def next_permutation[T <% Ordered[T]](a: Array[T]): Boolean = {
		return next_permutation(a,a.size)
	}
	def main(args: Array[String]) = {
		val N=6
		val b = new Breaks
		var r=0
		val e0=new Array[Int](N*2)
		val f0=new Array[Int](N*2)
		for(i<-Range(0,N)){e0(N+i)=1;f0(N+i)=1}
		val e=new Array[Int](N*2+1)
		val f=new Array[Int](N*2+1)
		do{
			for(i<-Range(0,N*2))e(i+1)=e(i)+e0(i)
			do{
				var x = 1
				b.breakable{
					for(i<-Range(0,N*2)){
						f(i+1)=f(i)+f0(i)
						if(e(i)==f(i)&&e(i+1)==f(i+1)){x=0;b.break}
					}
				}
				r+=x
			}while(next_permutation(f0))
		}while(next_permutation(e0))
		println(r);
	}
}

Fortran

implicit none
interface
subroutine reverse(a_,start_,size_)
	integer a_(*)
	integer start_,size_
end
logical function next_permutation(a_,n_)
	integer a_(:)
	integer n_
end
end interface
integer,parameter::N=6
integer r,i,x
integer e0(N*2)
integer f0(N*2)
integer e(N*2+1)
integer f(N*2+1)
do i=1,N
	e0(i)=0
	f0(i)=0
	e0(N+i)=1
	f0(N+i)=1
enddo
r=0
e(1)=0
f(1)=0
do while(.true.)
	do i=1,N*2
		e(i+1)=e(i)+e0(i)
	enddo
	do while(.true.)
		x=1
		do i=1,N*2
			f(i+1)=f(i)+f0(i)
			if((e(i).eq.f(i)).and.(e(i+1).eq.f(i+1))) then
				x=0
				exit
			endif
		enddo
		r=r+x
		if(.not.next_permutation(f0,size(f0))) exit
	enddo
	if(.not.next_permutation(e0,size(e0))) exit
enddo
write(*,"(i0)"),r
end

subroutine reverse(a_,start_,size_)
	integer a_(*)
	integer start_,size_
	integer end_,i_
	integer z_
	end_=start_+size_-1
	do i_=0,size_/2-1
		z_=a_(start_+i_)
		a_(start_+i_)=a_(end_-i_)
		a_(end_-i_)=z_
	end do
end

logical function next_permutation(a_,n_)
	integer a_(:)
	integer n_
	integer i_,k_,l_
	integer z_
	next_permutation=.false.
	if((0.le.n_).and.(n_.le.size(a_))) then
		call reverse(a_,n_,size(a_)+1-n_)
		i_=size(a_)-1
		do while(i_.ge.1)
			if(a_(i_).lt.a_(i_+1)) then
				exit
			endif
			i_=i_-1
		enddo
		if(i_.lt.1) then
			call reverse(a_,1,size(a_))
		else
			k_=i_
			i_=size(a_)
			do while(i_.ge.k_+1)
				if(a_(k_).lt.a_(i_)) then
					exit
				endif
				i_=i_-1
			enddo
			l_=i_;
			z_=a_(k_)
			a_(k_)=a_(l_)
			a_(l_)=z_
			call reverse(a_,k_+1,size(a_)+1-(k_+1))
			next_permutation=.true.
		endif
	endif
end

Pascal

{$apptype console} //Delphi6
program CodeIQRoute;
var
N:longint;
r:longint;
i:longint;
x:longint;
e0:array of longint;
f0:array of longint;
e:array of longint;
f:array of longint;

procedure reverse(var a:array of longint;start:longint;size:longint);
var
	en,i:longint;
	z:longint;
begin
	en:=start+size-1;
	for i:=0 to trunc(size/2-1) do begin
		z:=a[start+i];
		a[start+i]:=a[en-i];
		a[en-i]:=z;
	end;
end;

function next_permutation(var a:array of longint;n:longint):boolean;
var
	i,k,l:longint;
	z:longint;
begin
	next_permutation:=false;
	if (0<=n) and (n<=length(a)) then begin
		reverse(a,n,length(a)-n);
		i:=length(a)-2;
		while i>=0 do begin
			if a[i]<a[i+1] then break;
			i:=i-1;
		end;
		if i<0 then begin
			reverse(a,0,length(a));
		end else begin
			k:=i;
			i:=length(a)-1;
			while i>=k+1 do begin
				if a[k]<a[i] then break;
				i:=i-1;
			end;
			l:=i;
			z:=a[k];
			a[k]:=a[l];
			a[l]:=z;
			reverse(a,k+1,length(a)-(k+1));
			next_permutation:=true;
		end;
	end;
end;

begin
N:=6;
r:=0;
setlength(e0,N*2);
setlength(f0,N*2);
for i:=0 to N-1 do begin
	e0[N+i]:=1;
	f0[N+i]:=1;
end;
setlength(e,N*2+1);
setlength(f,N*2+1);
repeat
	for i:=0 to N*2-1 do e[i+1]:=e[i]+e0[i];
	repeat
		x:=1;
		for i:=0 to N*2-1 do begin
			f[i+1]:=f[i]+f0[i];
			if (e[i]=f[i]) and (e[i+1]=f[i+1]) then begin
				x:=0;
				break;
			end;
		end;
		r:=r+x;
	until not next_permutation(f0,length(f0));
until not next_permutation(e0,length(e0));
writeln(r);
end.