JavaScript
Go
R
Lua
dlang

今週のアルゴリズム:最短経路の計算!(D/Go/JavaScript/Lua/Rでnext_permutation)

More than 1 year has passed since last update.

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

C++
(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")