今週のアルゴリズム：最短経路の計算！(D/Go/JavaScript/Lua/Rで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参照)

D
std.algorithmを使わないほうが速かった。
それにしても 配列の長さの型がバージョンによって違う ってどういうことだろう。

#!/usr/bin/rdmd
import std.stdio, std.algorithm;
const int N=6;
void my_reverse(T)(T[] a,int start,int size){
	int end=start+size-1;
	for(;start<end;start++){
		T z=a[start];a[start]=a[end];a[end]=z;
		end--;
	}
}
bool my_next_permutation(T)(T[] a,int n){
	int siz=cast(int)a.length;
	if(n<0||siz<n)return false;
	int i;
	my_reverse(a,n,siz-n);
	for(i=cast(int)siz-2;i>=0;i--)if(a[i]<a[i+1])break;
	if(i<0){
		my_reverse(a,0,siz);
		return false;
	}
	int k=i;
	for(i=cast(int)siz-1;i>=k+1;i--)if(a[k]<a[i])break;
	int l=i;
	T z=a[k];a[k]=a[l];a[l]=z;
	my_reverse(a,k+1,siz-(k+1));
	return true;
}
bool my_next_permutation(T)(T[] a){
	return my_next_permutation(a,cast(int)a.length);
}
int main(){
	int r=0,i;
	int[] e0=new int[N*2],f0=new int[N*2];
	for(i=0;i<N;i++)e0[N+i]=f0[N+i]=1;
	int[N*2+1] e,f;
	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(my_next_permutation(f0));
		//}while(nextPermutation(f0));
	}while(my_next_permutation(e0));
	//}while(nextPermutation(e0));
	writeln(r);
	return 0;
}

Go

package main
import (
	"fmt"
	"sort"
)

func reverse(a sort.Interface,start int,size int){
	for end:=start+size-1;start<end;start++ {
		a.Swap(start,end)
		end--
	}
}
func next_permutation(a sort.Interface, n int) bool{
	if n<0||a.Len()<n {return false}
	reverse(a,n,a.Len()-n)
	i:=0
	for i=a.Len()-2;i>=0;i-- {if a.Less(i,i+1) {break}}
	if i<0 {
		reverse(a,0,a.Len())
		return false
	}
	k:=i
	for i=a.Len()-1;i>=k+1;i-- {if a.Less(k,i) {break}}
	l:=i
	a.Swap(k,l)
	reverse(a,k+1,a.Len()-(k+1))
	return true
}

func main(){
	N:=6
	e0:=make([]int,N*2)
	f0:=make([]int,N*2)
	i:=0
	r:=0
	for i=0;i<N;i++ {e0[N+i]=1;f0[N+i]=1}
	sort.Sort(sort.IntSlice(e0))
	sort.Sort(sort.IntSlice(f0))
	e:=make([]int,N*2+1);
	f:=make([]int,N*2+1);
	for {
		for i=0;i<N*2;i++ {e[i+1]=e[i]+e0[i]}
		for {
			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++}
			if !next_permutation(sort.IntSlice(f0),len(f0)) {break}
		}
		if !next_permutation(sort.IntSlice(e0),len(e0)) {break}
	}
	fmt.Println(r)
}

JavaScript

#!/usr/bin/node
var reverse=function(a,start,size){
	var end=start+size-1;
	for(;start<end;start++){
		var z=a[start];a[start]=a[end];a[end]=z;
		end--;
	}
}
var next_permutation=function(a,_n){
	var n=_n || a.length;
	if(n<0||a.length<n)return false;
	var i;
	reverse(a,n,a.length-n);
	for(i=a.length-2;i>=0;i--)if(a[i]<a[i+1])break;
	if(i<0){
		reverse(a,0,a.length);
		return false;
	}
	var k=i;
	for(i=a.length-1;i>=k+1;i--)if(a[k]<a[i])break;
	var l=i;
	var z=a[k];a[k]=a[l];a[l]=z;
	reverse(a,k+1,a.length-(k+1));
	return true;
}

var N=6;
var e0=[],f0=[],i,r=0;
for(i=0;i<N;i++){
	e0[i]=f0[i]=0;
	e0[N+i]=f0[N+i]=1;
}
var e=[0];
var f=[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];
			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.log(r);

Lua
Luaの配列って1からでしたっけ…？

#!/usr/bin/lua
reverse=function(a,start,size)
	local end_=start+size-1
	for i=0,size/2-1 do
		z=a[start+i]
		a[start+i]=a[end_-i]
		a[end_-i]=z
	end
end
next_permutation=function(a,n)
	if not n then n=#a end
	if n<0 or #a<n then
		return false
	end
	local i=0
	reverse(a,n,#a+1-n)
	i=#a-1
	while i>=1 do
		if a[i]<a[i+1] then break end
		i=i-1
	end
	if i<1 then
		reverse(a,1,#a)
		return false
	end
	local k=i
	i=#a
	while i>=k+1 do
		if a[k]<a[i] then break end
		i=i-1
	end
	local l=i
	local z=a[k]
	a[k]=a[l]
	a[l]=z
	reverse(a,k+1,#a+1-(k+1))
	return true
end

N=6
e0={}
f0={}
r=0
for i=1,N do
	e0[i]=0
	f0[i]=0
	e0[N+i]=1
	f0[N+i]=1
end
table.sort(e0)
table.sort(f0)
e={}
f={}
e[1]=0
f[1]=0
repeat
	for i=1,N*2 do
		e[i+1]=e[i]+e0[i]
	end
	repeat
		x=1
		for i=1,N*2 do
			f[i+1]=f[i]+f0[i]
			if e[i]==f[i] and e[i+1]==f[i+1] then
				x=0
				break
			end
		end
		r=r+x
	until not next_permutation(f0)
until not next_permutation(e0)
print(r)

R
とにかく遅い。Rはこういう処理には不向きな言語なのだということを改めて認識。

#!/usr/bin/Rscript
next_permutation<-function(env,name,n=NA){
	a=get(name,env)
	if(is.na(n))n<-length(a)
	if(n<0||length(a)<n)return(FALSE)
	i<-0
	a<-c(a[1:n],rev(a[-n:0]))
	for(i in rev(1:(length(a)-1)))if(a[i]<a[i+1])break # r doesn't go beyond the range
	if(a[i]>=a[i+1]){
		assign(name,rev(a),env)
		return(FALSE)
	}
	k<-i
	for(i in rev((k+1):length(a)))if(a[k]<a[i])break
	l<-i
	z<-a[k];a[k]<-a[l];a[l]<-z
	assign(name,a<-c(a[1:k],rev(a[-k:0])),env)
	return(TRUE)
}

env<-new.env()
N<-6
e0<-1:(N*2)
f0<-1:(N*2)
i<-0
r<-0
for(i in 1:N){
	e0[i]=f0[i]=0
	e0[N+i]=f0[N+i]=1
}
e=0:(N*2)
f=0:(N*2)
assign("e0",e0,env)
assign("f0",f0,env)
repeat{
	e0=get("e0",env)
	for(i in 1:(N*2))e[i+1]<-e[i]+e0[i]
	repeat{
		f0=get("f0",env)
		x<-1
		for(i in 1:(N*2)){
			f[i+1]<-f[i]+f0[i]
			if(e[i]==f[i]&&e[i+1]==f[i+1]){x<-0;break}
		}
		r<-r+x
		if(!next_permutation(env,"f0"))break
	}
	if(!next_permutation(env,"e0"))break
}
cat(r)
cat("\n")