LoginSignup
11
11

More than 3 years have passed since last update.

@cielavenir

今週のアルゴリズム：最短経路の計算！(Ruby/Python/C#/VB/Goでpermutation iterator)

Last updated at Posted at 2013-12-25

問題 https://codeiq.jp/ace/thisweek_masuipeo/q608
Permission Granted as https://twitter.com/masuipeo/status/410915846987345920
まとめ https://github.com/cielavenir/procon/commit/9eab68d94840331618eb8e4c07b84fb0c0adb8b0

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参照)
言語 タイム
C++ (clang++ -O2) 0.02s
C++ (g++-mp-4.8 -O2) 0.02s
D 0.11s
Fortran (gfortran) 0.14s
Fortran (g95) 0.14s
JavaScript 0.16s
C++ (clang++) 0.17s
Go (go build) 0.19s
Java 0.22s
Pascal (fpc) 0.22s
C++ (g++-mp-4.8) 0.28s
C# 0.33s
Nemerle 0.39s (ideone)
Go (go run) 0.45s
Go (iter/go build) 0.53s
VB.Net 0.57s (ideone)
Go (iter/go run) 0.78s
C# (iter) 0.89s
VB.Net (iter) (別マシンのため計測不可)
Boo (booc) 1.44s
Scala 1.92s
Boo (booi) 2.59s
Ruby (iter) 2.97s
PHP 5.24s
Lua 5.53s (ideone)
Perl (iter) 6.33s
Perl (next) 6.59s
Groovy 9.15s
Ruby (next) 11.15s
Python 15.91s
Python (iter) 16.12s
Python3 (iter) 16.37s
Python3 16.43s
HSP 20.32s
R 98.06s
Perl6 58m

コンパイルを必要としない言語の中ではGoやJavaScriptが群を抜いて速いです。
あとRubyもがんばってる。
rdmdは内部的にコンパイルしてますから2回目以降は速い。
Booの方が若干早いようだけど、Booは型付けが面倒だからなぁ。C#のほうがまし。速いし。
それにしても、Rが遅いですね…。

[140104追記] Perl6やばすぎです…。w

言語が使えるというからにはnext_permutationぐらい書けないとだめよねってことで、20言語でnext_permutationを書く企画をやってました(笑)
発端は、Rubyの

#!/usr/bin/ruby
class Array
    def unique_permutation(n=self.size)
        return to_enum(:permutation2,n) unless block_given?
        return if n<0||self.size<n
        a=self.sort
        yield a[0,n]
        while true
            a=a[0,n]+a[n..-1].reverse
            k=(a.size-2).downto(0).find{|i|a[i]<a[i+1]}
            break if !k
            l=(a.size-1).downto(k+1).find{|i|a[k]<a[i]}
            a[k],a[l]=a[l],a[k]
            a=a[0,k+1]+a[k+1..-1].reverse
            yield a[0,n]
        end
    end
    def partial_sum
=begin
        s=[0]
        0.step(self.size-1){|i|s<<s[i]+self[i]}
        s
=end
        self.reduce([0]){|s,e|s<<s.last+e}
    end
end

N=6
P=([0]*N+[1]*N).unique_permutation.to_a # N=5のとき、permutation.to_a.uniqの70倍速
#各Pは経路を表す。1が縦、0が横を表す。
r=0
i=0
e=[0]*(N*2+1)
f=[0]*(N*2+1)
P.each{|e0|
    (N*2).times{|i|e[i+1]=e[i]+e0[i]}
    #数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。
    P.each{|f0|
        r+=1 if (N*2).times.none?{|i|
            f[i+1]=f[i]+f0[i]
            #i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。
            e[i]==f[i] && e[i+1]==f[i+1]
        }
    }
}
p r # 100360

これが、Array#permutationよりも著しく速かったことによります。というかpermutation.to_a.uniqだとそもそもメモリ不足で実行できなかった。
なので、重複を除くpermutationを書いてみました。

Python

#!/usr/bin/python
#coding:utf-8
import sys
if sys.version_info[0]>=3: from functools import reduce

def find(cond,a):
    for e in a:
        if cond(e): return e
    return None
def permutation(x,n=None):
    if n==None: n=len(x)
    if n<0 or len(x)<n: return
    a=sorted(x)
    yield tuple(a[0:n])
    while True:
        a=a[0:n]+a[len(a)-1:n-1:-1]
        k=find(lambda i: a[i]<a[i+1], range(len(a)-2,-1,-1))
        if k==None: break
        l=find(lambda i: a[k]<a[i], range(len(a)-1,k,-1))
        a[k],a[l]=a[l],a[k]
        a=a[0:k+1]+a[len(a)-1:k:-1]
        yield tuple(a[0:n])

N=6
e0=[0]*N+[1]*N
f0=[0]*N+[1]*N
#各Pは経路を表す。1が縦、0が横を表す。
r=0
i=0
e=[0]*(N*2+1)
f=[0]*(N*2+1)
for _e in permutation(e0):
    for i in range(N*2): e[i+1]=e[i]+_e[i]
    #e=reduce(lambda s,_: (s.append(s[-1:][0]+_),s)[1],e0,[0])
    #数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。
    for _f in permutation(f0):
        for i in range(N*2): f[i+1]=f[i]+_f[i]
        #f=reduce(lambda s,_: (s.append(s[-1:][0]+_),s)[1],f0,[0])
        if all(e[i]!=f[i] or e[i+1]!=f[i+1] for i in range(N*2)): r+=1
        #i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。
print(r) # 100360

C#

using System;
using System.Collections.Generic;
class CodeIQRoute{
    static IEnumerable<List<T>> Permutation<T>(List<T> x,int? _n=null) where T : IComparable<T>{
        int n=_n ?? x.Count;
        if(n<0||x.Count<n)yield break;
        List<T> a=new List<T>(x);
        a.Sort();
        yield return a.GetRange(0,n);
        for(;;){
            int i;
            a.Reverse(n,a.Count-n);
            for(i=a.Count-2;i>=0;i--)if(a[i].CompareTo(a[i+1])<0)break;
            if(i<0){
                //a.Reverse(0,a.Count);
                /*yield*/ break;
            }
            int k=i;
            for(i=a.Count-1;i>=k+1;i--)if(a[k].CompareTo(a[i])<0)break;
            int l=i;
            T z=a[k];a[k]=a[l];a[l]=z;
            a.Reverse(k+1,a.Count-(k+1));
            yield return a.GetRange(0,n);
        }
    }
    const int N=6;
    public static void Main(){
        int r=0,i;
        List<int>e0=new List<int>(),f0=new List<int>();
        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];
        foreach(List<int> _e in Permutation(e0)){
            for(i=0;i<N*2;i++)e[i+1]=e[i]+_e[i];
            foreach(List<int> _f in Permutation(f0)){
                for(i=0;i<N*2;i++){
                    f[i+1]=f[i]+_f[i];
                    if(e[i]==f[i]&&e[i+1]==f[i+1])break;
                }
                if(i==N*2)r++;
            }
        }
        Console.WriteLine(r);
    }
}

VB.Net

imports System
imports System.Collections.Generic
module CodeIQRoute
    iterator function permutation(of T as IComparable)(ByVal x as List(of T),optional ByVal _n as integer?=Nothing) as IEnumerable(of List(of T))
        dim n as integer=if(_n.HasValue,_n,x.Count)
        if n<0 orelse x.Count<n
            return
        end If
        dim a as List(of T)=new List(of T)(x)
        a.Sort()
        dim i as integer
        yield a.GetRange(0,n)
        while true
            a.Reverse(n,a.Count-n)
            for i=a.Count-2 to 0 step -1
                if a(i).CompareTo(a(i+1))<0
                    exit for
                end if
            next
            if i<0
                a.Reverse(0,a.Count)
                return
            end if
            dim k as integer=i
            for i=a.Count-1 to k+1 step -1
                if a(k).CompareTo(a(i))<0
                    exit for
                end if
            next
            dim l as integer=i
            dim z as T=a(k):a(k)=a(l):a(l)=z
            a.Reverse(k+1,a.Count-(k+1))
            yield a.GetRange(0,n)
        end while
    end function

    const N=6
    sub Main(ByVal args() as String)
        dim r,i as integer
        dim e0 as List(of integer)=new List(of integer)()
        dim f0 as List(of integer)=new List(of integer)()
        for i=0 to N-1
            e0.Add(0)
            f0.Add(0)
        next
        for i=0 to N-1
            e0.Add(1)
            f0.Add(1)
        next
        dim e as integer()=new integer(N*2){}
        dim f as integer()=new integer(N*2){}
        for each _e as List(of integer) in permutation(e0)
            for i=0 to N*2-1
                e(i+1)=e(i)+_e(i)
            next
            for each _f as List(of integer) in permutation(f0)
                for i=0 to N*2-1
                    f(i+1)=f(i)+_f(i)
                    if e(i)=f(i) andalso e(i+1)=f(i+1)
                        exit for
                    end if
                next
                if i=N*2
                    r+=1
                end if
            next
        next
        Console.WriteLine(r)
    end sub
end module

Go
ジェネリクスがないのでやや汚い。リフレクションの復習を兼ねてみた。

package main
import (
    "fmt"
    "sort"
    "reflect"
)

/*
func compare(a interface{},b interface{}) int{ // a and b must have the same type. If different, runtime error will be triggered. will be fixed after generics is introduced.
    switch reflect.ValueOf(a).Kind() {
        case reflect.Int:
            n1:=reflect.ValueOf(a).Int()
            n2:=reflect.ValueOf(b).Int()
            if n1<n2 {return -1} else if n1>n2 {return 1} else {return 0}
        case reflect.Float32: case reflect.Float64:
            n1:=reflect.ValueOf(a).Float()
            n2:=reflect.ValueOf(b).Float()
            if n1<n2 {return -1} else if n1>n2 {return 1} else {return 0}
        case reflect.String:
            n1:=reflect.ValueOf(a).String()
            n2:=reflect.ValueOf(b).String()
            if n1<n2 {return -1} else if n1>n2 {return 1} else {return 0}
    }
    return 0 //lol
}
func reflect_reverse(a reflect.Value,start int,size int){
    for end:=start+size-1;start<end;start++ {
        z:=a.Index(start).Interface()
        a.Index(start).Set(a.Index(end))
        a.Index(end).Set(reflect.ValueOf(z))
        end--
    }
}
func permutation(x interface{}, n int) <- chan reflect.Value{
    ch := make(chan reflect.Value)
    go func(){
        if 0<=n&&n<=reflect.ValueOf(x).Len() {
            a:=reflect.MakeSlice(reflect.TypeOf(x),reflect.ValueOf(x).Len(),reflect.ValueOf(x).Len())
            reflect.Copy(a,reflect.ValueOf(x))
            //sort.Sort(sort.IntSlice(a)); //interface{} cannot be sorted, so you must sort the array prior.
            ch <- a
            for {
                reflect_reverse(a,n,a.Len()-n)
                i:=0
                for i=a.Len()-2;i>=0;i-- {if compare(a.Index(i).Interface(),a.Index(i+1).Interface())<0 {break}}
                if i<0 {
                    //reflect_reverse(a,0,a.Len())
                    break
                }
                k:=i
                for i=a.Len()-1;i>=k+1;i-- {if compare(a.Index(k).Interface(),a.Index(i).Interface())<0 {break}}
                l:=i
                z:=a.Index(k).Interface()
                a.Index(k).Set(a.Index(l))
                a.Index(l).Set(reflect.ValueOf(z))
                reflect_reverse(a,k+1,a.Len()-(k+1))
                ch <- a
            }
        }
        close(ch)
    }()
    return ch
}
*/
func reverse(a sort.Interface,start int,size int){
    for end:=start+size-1;start<end;start++ {
        a.Swap(start,end)
        end--
    }
}
func permutation(a sort.Interface, n int) <- chan reflect.Value{
    ch := make(chan reflect.Value)
    go func(){
        if 0<=n&&n<=a.Len() {
            sort.Sort(a); // a is modified directly, so never write to it within the block
            ch <- reflect.ValueOf(a)
            for {
                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())
                    break
                }
                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))
                ch <- reflect.ValueOf(a)
            }
        }
        close(ch)
    }()
    return ch
}

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}
    e:=make([]int,N*2+1);
    f:=make([]int,N*2+1);
    for _e:=range permutation(sort.IntSlice(e0),len(e0)) {
        for i=0;i<N*2;i++ {e[i+1]=e[i]+_e.Index(i).Interface().(int)}
        for _f:=range permutation(sort.IntSlice(f0),len(f0)) {
            for i=0;i<N*2;i++ {
                f[i+1]=f[i]+_f.Index(i).Interface().(int)
                if e[i]==f[i]&&e[i+1]==f[i+1] {break}
            }
            if i==N*2 {r++}
        }
    }
    fmt.Println(r)
}
11
11
1

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
11
11