permutation.eachを自前で用意する(rubyで魔方陣その４)

permutation.eachを自前で用意する

Counting And Listing All PermutationsのB. Heap's algorithmを元にされたGaucheで魔方陣に挑戦(順列を実装) - Gemmaの日記のu8.scmのアルゴリズムをrubyに実装してみた。

def heapPermute(n,item,block=Proc.new)
  if n==1
    block.call(item)
  else
    0.upto(n-1){|i|
      heapPermute(n-1,item,block)
      n%2==0 ? swap(0,n-1,item) : swap(i,n-1,item)
    }
  end
end

def swap(a,b,item)
  tmp=item[a]
  item[a]=item[b]
  item[b]=tmp
end

item=(1..9).to_a
heapPermute(9,item){|i|
  x=i[0]+i[1]+i[2]
  p i if x==i[3]+i[4]+i[5]&&x==i[6]+i[7]+i[8]&&x==i[0]+i[3]+i[6]&&x==i[1]+i[4]+i[7]&&x==i[2]+i[5]+i[8]&&x==i[0]+i[4]+i[8]&&x==i[2]+i[4]+i[6]
}

コードがlisp臭くなっているのがすごく気に入らないんだが、Proc.callじゃなくてyieldで書きたいがその時どうやって再帰の方に引数を渡すのか分からないのでこのまま行ってみる。

$ time ruby e.rb
[8, 3, 4, 1, 5, 9, 6, 7, 2]
[8, 1, 6, 3, 5, 7, 4, 9, 2]
[6, 7, 2, 1, 5, 9, 8, 3, 4]
[6, 1, 8, 7, 5, 3, 2, 9, 4]
[4, 3, 8, 9, 5, 1, 2, 7, 6]
[4, 9, 2, 3, 5, 7, 8, 1, 6]
[2, 7, 6, 9, 5, 1, 4, 3, 8]
[2, 9, 4, 7, 5, 3, 6, 1, 8]

real	0m0.650s
user	0m0.636s
sys	0m0.008s

そして、Gaucheでかかれたu8.scmの方は

u$ time gosh u8.scm
#u8(2 9 4 7 5 3 6 1 8)
#u8(2 7 6 9 5 1 4 3 8)
#u8(4 3 8 9 5 1 2 7 6)
#u8(4 9 2 3 5 7 8 1 6)
#u8(6 7 2 1 5 9 8 3 4)
#u8(6 1 8 7 5 3 2 9 4)
#u8(8 3 4 1 5 9 6 7 2)
#u8(8 1 6 3 5 7 4 9 2)

real	0m0.847s
user	0m0.828s
sys	0m0.004s

（スーパーサイ○人になる前でも）差が生じるのは言語のせいとは言いたくないんだけど…言語の特性なるものがあるんだろうか。
というか、もっとschemeくさくコード書くと高速化するのでしょうか?
私の技術ではまだ無理そうだなぁ…

追記 2008/12/13 22:37:18:

id:Gemmaさんの方でvectorでインプリメントされ直してあった（笑
そのコードの実行結果

$ time gosh k.scm
#(2 9 4 7 5 3 6 1 8)
#(2 7 6 9 5 1 4 3 8)
#(4 3 8 9 5 1 2 7 6)
#(4 9 2 3 5 7 8 1 6)
#(6 7 2 1 5 9 8 3 4)
#(6 1 8 7 5 3 2 9 4)
#(8 3 4 1 5 9 6 7 2)
#(8 1 6 3 5 7 4 9 2)

real	0m0.433s
user	0m0.432s
sys	0m0.008s

さすがなスピード（笑

ここまで

odd?使って遅くなったのはナイショ（笑

もうちょっとrubyっぽくかくとこうなるけどおそくなった。

class Permute
  def initialize(item) @item=item ;end
  def each(block=Proc.new) heapPermute(@item.size,block) ;end
  def heapPermute(n,block=Proc.new)
    if n==1
    block.call(@item)
    else
      0.upto(n-1){|i|
        heapPermute(n-1,block)
        n%2==0 ? swap(0,n-1) : swap(i,n-1)
      }
    end
  end
  def swap(a,b)
    tmp=@item[a]
    @item[a]=@item[b]
    @item[b]=tmp
  end
  protected :heapPermute, :swap
end

Permute.new((1..9).to_a).each{|i|
  x=i[0]+i[1]+i[2]
  p i if x==i[3]+i[4]+i[5]&&x==i[6]+i[7]+i[8]&&x==i[0]+i[3]+i[6]&&x==i[1]+i[4]+i[7]&&x==i[2]+i[5]+i[8]&&x==i[0]+i[4]+i[8]&&x==i[2]+i[4]+i[6]
}