LoginSignup
5
5

More than 3 years have passed since last update.

@cielavenir

今週のアルゴリズム：最短経路の計算！(Java/Groovy/Scala/Fortran/Pascalでnext_permutation)

Last updated at Posted at 2013-12-25
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.
5
5
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
5