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