今週のアルゴリズム：最短経路の計算！(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<br>Kotlin/Nim/Perl/Perl6|([github](https://github.com/cielavenir/codeiq_solutions/tree/master/thisweek_masuipeo/q608)参照)|

## Go2

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

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

```go: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されていないんだろう。。

```cr: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対応しています

```kotlin: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

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

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