Go to Qiita Advent Calendar Top
LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@cielavenir

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

Last updated at Posted at 2021-03-23
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
2
1
0

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
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?