From: Dai Watanabe <dai@...>
Date: 2003-04-11T18:59:28+09:00
Subject: [ruby-list:37550] 順列イテレータ

はじめまして。わたなべ＠ひたちです。

Rubyを使い始めたところで、使いやすさ・奥の深さに感動しっぱなし
です。今後ともよろしく御願いいたします。

ちょっと必要にかられて順列生成のコードを探してみたのですが、
イテレータの例が見つからなかったのでArrayクラスの拡張として自作してみました。

再帰を使ったので、呼び出し部と処理本体を区別し、また、配列を複製する方法しか
思いつかなかったのですが、スマートな実装は可能なのでしょうか？

以下がコードです。
呼び出し部を分けたついでに、要素の重複を区別しないという順列イテレータ
にもなるようにしてみました。

------
class  Array
	 def perm_body(r_ary,n, opt )
		if n == 0
			yield r_ary
		elsif n > 0
			lst = opt ? self.uniq : self
			 lst.each_index do |i|
			 	r_ary.push( lst.at( i ) )
			 	b = self.dup
			 	b.delete_at( opt ? b.index(lst.at(i)) : i )
			 	b.perm_body(r_ary,n-1,opt){ |arry| yield arry }
			 	r_ary.pop
			 end
		else
			# nop
		end
	 end

	 def perm( n = self.size )
		n = self.size if n > self.size
		self.perm_body([],n, nil) { |arry| yield arry }
	 end

	 def perm2( n = self.size )
		n = self.size if n > self.size
		self.perm_body([],n, true ) { |arry| yield arry }
	 end
end

##### sample code ########
ary = [ ]
cnt = 0
ary.perm  { |ar| p ar; cnt+= 1 }
print "empty array called proc #{cnt} times \n\n"

ary = [ "foo", "bar" ]
ary.perm  { |ar| p ar}
puts "\n"

ary = [ "one" , 2 , "three" ]
cnt = 0
ary.perm  { |ar| p ar; cnt+=1}
print "array called proc #{cnt} times \n\n"

ary = %w{ Nozomi Hikari Kodama Nozomi }
ary.perm  { |ar| p ar.join( " --> " )} ; puts "\n"
ary.perm(2)  { |ar| p ar.join( " --> " )} ; puts "\n"
ary.perm(0)  { |ar| p ar.join( " --> " )} ; puts "\n"
ary.perm2  { |ar| p ar.join( " --> " )} ; puts "\n"
ary.perm2(2)  { |ar| p ar.join( " --> " )} ; puts "\n"

t_s = Time.now
ary = [ 1, 2,3,4,5,6,7,8 ]

print "\n calling perm-method... array size:#{ary.size} \n"

cnt=0
ary.perm  { cnt += 1  }

t_e = Time.now
tm = t_e - t_s
print "called #{cnt}, total_time:#{tm},  #{tm/cnt}sec/call\n"