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

問題 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<br>Kotlin/Nim/Perl/Perl6|([github](https://github.com/cielavenir/codeiq_solutions/tree/master/thisweek_masuipeo/q608)参照)|

|言語|タイム|
|:--|:--|
|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の

```rb
#!/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

```py
#!/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#

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

```vbnet
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
ジェネリクスがないのでやや汚い。リフレクションの復習を兼ねてみた。

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