This Week's Algorithm: Shortest Path Calculation! (Permutation iterator in Ruby / Python / C # / VB / Go)

Problem https://codeiq.jp/ace/thisweek_masuipeo/q608 Permission Granted as https://twitter.com/masuipeo/status/410915846987345920 Summary https://github.com/cielavenir/procon/commit/9eab68d94840331618eb8e4c07b84fb0c0adb8b0

Go and JavaScript are by far the fastest of the languages that don't require compilation. Also Ruby is doing its best. Since rdmd is compiled internally, it is fast after the second time. Boo seems to be a little faster, but Boo is troublesome to type. C # is better. It's fast. Even so, R is slow ...

[140104 postscript] Perl6 is too bad ... w

Since I can use languages, I have to write next_permutation, so I was planning to write next_permutation in 20 languages (laugh) It all started with 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=When it is 5, permutation.to_a.70 times faster than uniq
#Each P represents a route. 1 is vertical and 0 is horizontal.
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]}
	#Assuming that the lower left is A and the upper right is B as in the mathematical coordinate system, the x coordinate is i at each index i of e.-e[i], Y coordinate is e[i]Will be.
	P.each{|f0|
		r+=1 if (N*2).times.none?{|i|
			f[i+1]=f[i]+f0[i]
			#i-th coordinate and i+If the first coordinates are equal, it can be considered that there is an overlap in the road.
			e[i]==f[i] && e[i+1]==f[i+1]
		}
	}
}
p r # 100360

This is because it was significantly faster than Array # permutation. Or rather, permutation.to_a.uniq couldn't be executed due to lack of memory in the first place. So I wrote a permutation that eliminates duplication.

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
#Each P represents a route. 1 is vertical and 0 is horizontal.
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])
	#Assuming that the lower left is A and the upper right is B as in the mathematical coordinate system, the x coordinate is i at each index i of e.-e[i], Y coordinate is e[i]Will be.
	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-th coordinate and i+If the first coordinates are equal, it can be considered that there is an overlap in the road.
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 It's a little dirty because there is no generics. I also tried to review the reflection.

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