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
Permutation Iterator | next_permutation | URL |
---|---|---|
C#/Go/Python/Ruby/VB | Summary including 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 |
C/C++/Perl/Perl6 | (See github) |
language | time |
---|---|
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) | (Cannot be measured because it is a separate machine) |
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 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)
}
Recommended Posts