Java
Scala
Fortran
Groovy
Pascal

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

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.