Der Algorithmus dieser Woche: Berechnen Sie den kürzesten Weg! (Permutationsiterator in Ruby / Python / C # / VB / Go)

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

Go und JavaScript sind bei weitem die schnellsten Sprachen, die nicht kompiliert werden müssen. Auch Ruby gibt sein Bestes. Da rdmd intern kompiliert wird, ist es nach dem zweiten Mal schnell. Boo scheint etwas schneller zu sein, aber Boo ist mühsam zu tippen. C # ist besser. Es ist schnell. Trotzdem ist R langsam ...

[140104 postscript] Perl6 ist schade ... w

Da ich Sprachen verwenden kann, muss ich über next_permutation schreiben, also hatte ich vor, next_permutation in 20 Sprachen zu schreiben (lacht) Alles begann mit 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=Wenn 5, Permutation.to_a.70 mal schneller als uniq
#Jedes P repräsentiert eine Route. 1 ist vertikal und 0 ist 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]}
	#Angenommen, die untere linke Seite ist A und die obere rechte Seite ist B wie im mathematischen Koordinatensystem, dann ist die x-Koordinate i an jedem Index i von e.-e[i]Die Y-Koordinate ist e[i]Wird sein.
	P.each{|f0|
		r+=1 if (N*2).times.none?{|i|
			f[i+1]=f[i]+f0[i]
			#i-te Koordinate und i+Wenn die ersten Koordinaten gleich sind, kann davon ausgegangen werden, dass sich die Straße überlappt.
			e[i]==f[i] && e[i+1]==f[i+1]
		}
	}
}
p r # 100360

Dies liegt daran, dass es erheblich schneller als die Array # -Permutation war. Tatsächlich konnte permutation.to_a.uniq aufgrund von Speichermangel überhaupt nicht ausgeführt werden. Also habe ich eine Permutation geschrieben, die Doppelarbeit eliminiert.

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
#Jedes P repräsentiert eine Route. 1 ist vertikal und 0 ist 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])
	#Angenommen, die untere linke Seite ist A und die obere rechte Seite ist B wie im mathematischen Koordinatensystem, dann ist die x-Koordinate i an jedem Index i von e.-e[i]Die Y-Koordinate ist e[i]Wird sein.
	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-te Koordinate und i+Wenn die ersten Koordinaten gleich sind, kann davon ausgegangen werden, dass sich die Straße überlappt.
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 Es ist ein bisschen schmutzig, weil es keine Generika gibt. Ich habe auch versucht, die Reflexion zu überprüfen.

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