今週のアルゴリズム：最短経路の計算！(Go2/Crystal/Kotlin/Nim/Juliaでpermutation iterator)

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参照)

Go2

ジェネリクスにより、sort.Interfaceを使って頑張る必要がなくなった。ありがたい。

というかこの記事の更新をしようと思ったのはジェネリクスのおかげ--;;;

tyama_codeiq608_iter.go2

//usr/bin/env go run $0 $@;exit
package main
import "constraints"
import "fmt"

func reverse[T any](a []T,start int,size int){
    for end:=start+size-1;start<end;start++ {
        z:=a[start]
        a[start]=a[end]
        a[end]=z
        end--
    }
}
func permutation[T constraints.Ordered](x []T, n int) <- chan []T{
    ch := make(chan []T)
    go func(){
        if 0<=n&&n<=len(x) {
            a:=make([]T,n)
            for i:=0;i<n;i++ {a[i]=x[i]}
            for {
                {
                    b:=make([]T,n)
                    for i:=0;i<n;i++ {b[i]=a[i]}
                    ch <- b
                }
                reverse(a,n,len(a)-n)
                i:=0
                for i=len(a)-2;i>=0;i-- {if a[i]<a[i+1] {break}}
                if i<0 {
                    //reverse(a,0,len(a))
                    break
                }
                k:=i
                for i=len(a)-1;i>=k+1;i-- {if a[k]<a[i] {break}}
                l:=i
                z:=a[k]
                a[k]=a[l]
                a[l]=z
                reverse(a,k+1,len(a)-(k+1))
            }
        }
        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[int](e0,len(e0)) {
        for i=0;i<N*2;i++ {e[i+1]=e[i]+_e[i]}
        for _f:=range permutation[int](f0,len(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++}
        }
    }
    fmt.Println(r)
}

Crystal

RubyにはEnumerator.new{|y|}があるけどCrystalにはない。Channel(T)にinclude Iterator(T)させれば良いと思った。なんで標準でincludeされていないんだろう。。

tyama_codeiq608_iter.cr

#!/usr/bin/env crystal
class Array(T)
    def unique_permutation(n=self.size) : Channel(Array(T))
        nxt=Channel(Array(T)).new
        spawn{
            if n<0||self.size<n
                nxt.close
                next
            end
            a=self.sort
            nxt.send a[0,n]
            loop{
                a=a[0,n]+a[n..-1].reverse
                k=(a.size-2).downto(0).find{|i|a[i]<a[i+1]}
                if k.is_a?(Nil)
                    nxt.close
                    break
                end
                l=(a.size-1).downto(k+1).find{|i|a[k]<a[i]}.not_nil!
                a[k],a[l]=a[l],a[k]
                a=a[0,k+1]+a[k+1..-1].reverse
                nxt.send a[0,n]
            }
        }
        nxt
    end
    def partial_sum
        self.reduce([0]){|s,e|s << s.last+e}
    end
end

class Channel(T)
    include Iterator(T)
    def next
        begin
            receive
        rescue ClosedError
            stop
        end
    end
end

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

Kotlin

fun <T: Comparable<T>>を使う点以外は多段階選抜の答案を見ながらさくっと。
※いつものことながらkotlin-native対応しています

tyama_codeiq608_iter.kt

//usr/bin/env kscript $0 $@;exit
fun <T>reverse(a: Array<T>,start: Int,size: Int){
    val end=start+size-1
    for(i in 0..size/2-1){
        val z=a[start+i]
        a[start+i]=a[end-i]
        a[end-i]=z
    }
}
fun <T: Comparable<T>>unique_permutation(a0: Array<T>,n: Int):Sequence<Array<T>>{
    return sequence seq@{
        if(n<0||a0.size<n)return@seq
        var a=a0.copyOf()
        while(true){
            yield(a.sliceArray(0..n-1))
            reverse(a,n,a.size-n)
            var k = -1
            for(i in (a.size-2) downTo 0 step 1)if(a[i]<a[i+1]){k=i;break}
            if(k<0){
                //reverse(a,0,a.size)
                break
            }
            var l = -1
            for(i in a.size-1 downTo k+1 step 1)if(a[k]<a[i]){l=i;break}
            val z=a[k];a[k]=a[l];a[l]=z
            reverse(a,k+1,a.size-(k+1))
        }
    }
}
fun <T: Comparable<T>>unique_permutation(a: Array<T>):Sequence<Array<T>>{
    return unique_permutation(a,a.size)
}
fun main(args: Array<String>){
    val N=6
    var r=0
    val e0=Array<Int>(N*2){0}
    val f0=Array<Int>(N*2){0}
    for(i in 0..N-1){e0[N+i]=1;f0[N+i]=1}
    val e=Array<Int>(N*2+1){0}
    val f=Array<Int>(N*2+1){0}
    for(e_ in unique_permutation(e0)){
        for(i in 0..N*2-1)e[i+1]=e[i]+e_[i]
        for(f_ in unique_permutation(f0)){
            run outer@{
                for(i in 0..N*2-1){
                    f[i+1]=f[i]+f_[i]
                    if(e[i]==f[i]&&e[i+1]==f[i+1])return@outer
                }
                r++
            }
        }
    }
    println(r)
}

Nim

tyama_codeiq608_iter.nim

#[
/usr/bin/env nim c --nimcache:$HOME/.nimcache --opt:speed --run $0 $@;exit
#]#

import algorithm
import sequtils

proc unique_permutation[T](a0:seq[T],n0:ref int=nil):iterator:seq[T] =
 return iterator:seq[T] =
  var n=len(a0)
  if n0!=nil:
   n=n0[]
  if n<0 or len(a0)<n: return
  var a=a0.sorted
  yield a[0..n-1]
  while true:
   a=concat(a[0..n-1],a[n..len(a)-1].reversed)
   var k = -1
   block blk:
    for i in countdown(len(a)-2,0):
     if a[i]<a[i+1]:
      k=i
      break blk
    #a.reverse
    return
   for l in countdown(len(a)-1,k):
    if a[k]<a[l]:
     let z=a[k]
     a[k]=a[l]
     a[l]=z
     break
   a=concat(a[0..k],a[k+1..len(a)-1].reversed)
   yield a[0..n-1]

let N=6
var e0=concat(repeat(0,N),repeat(1,N))
var f0=concat(repeat(0,N),repeat(1,N))
#各Pは経路を表す。1が縦、0が横を表す。
var r=0
var e=repeat(0,N*2+1)
var f=repeat(0,N*2+1)
for e1 in unique_permutation(e0):
 for i in countup(0,N*2-1): e[i+1]=e[i]+e1[i]
 #数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。
 for f1 in unique_permutation(f0):
  for i in countup(0,N*2-1): f[i+1]=f[i]+f1[i]
  block blk:
   for i in countup(0,N*2-1):
    if e[i]==f[i] and e[i+1]==f[i+1]:
     break blk
   r+=1
   #i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。
writeLine(stdout,r) # 100360

Julia

tyama_codeiq608_iter.jl

#!/usr/bin/env julia

function reverse(a,start::Int,size::Int)
    local end_=start+size-1
    while start<end_
        local z=a[start]
        a[start]=a[end_]
        a[end_]=z
        end_-=1
        start+=1
    end
end

function next_permutation(a0,n::Int)
    local ch = Channel{typeof(a0)}(8)
    function _producer()
        if n<0||length(a0)<n
            close(ch)
            return
        end
        local a=a0[:]
        while true
            put!(ch,a[1:n])
            reverse(a,n+1,length(a)-n)
            local i=length(a)-1
            while i>0
                if a[i]<a[i+1]
                    break
                end
                i-=1
            end
            if i<=0
                #reverse(a,1,length(a))
                break
            end
            local k=i
            i=length(a)
            while i>=k
                if a[k]<a[i]
                    break
                end
                i-=1
            end
            local l=i
            local z=a[k]
            a[k]=a[l]
            a[l]=z
            reverse(a,k+1,length(a)+1-(k+1))
        end
        close(ch)
    end
    @async _producer()
    return ch
end

Base.@ccallable function julia_main(args::Vector{String})::Cint
    local N=6
    local e0=Array{Int}(undef,N*2)
    local f0=Array{Int}(undef,N*2)
    local i=1
    local r=0
    while i<=N
        e0[N+i]=1
        f0[N+i]=1
        i+=1
    end
    sort!(e0)
    sort!(f0)
    local e=Array{Int}(undef,N*2+1)
    local f=Array{Int}(undef,N*2+1)
    for e_ in next_permutation(e0,length(e0))
        for i in 1:N*2
            e[i+1]=e[i]+e_[i]
        end
        for f_ in next_permutation(f0,length(f0))
            i=1
            while i<=N*2
                f[i+1]=f[i]+f_[i]
                if e[i]==f[i]&&e[i+1]==f[i+1]
                    break
                end
                i+=1
            end
            if i>N*2
                r+=1
            end
        end
    end
    println(r)
    return 0
end

if get(ENV, "COMPILE_STATIC", "false") == "false"
    julia_main(ARGS)
end