順列プログラムの動作確認(1) - わさっきについて,Rubyのみでの検証プログラムを書いておきます.
#!/usr/bin/env ruby # permutation4.rb $KCODE='u' require 'permutation3.rb' class Permutation # 出力が正しいか確認する def verify c = 0 # 個数 s_last = "" self.each do |s| c += 1 if s.split(//u).sort.join('') != @seed_s return "NG" end if c > 1 and !(s_last < s) return "NG" end s_last = s end if c != self.total return "NG" end "OK" end end if __FILE__ == $0 str = ARGV.shift || 'ABCD' puts Permutation.new(str).verify end
順列を順番にすべて - わさっきに掲載したpermutation3.rbを取り込んでいます.2箇所ある「self.」は,取り除いても動作しますが,気分でつけています.
判定条件は,以下のように変えています.
- 総数が正しい.すなわち,eachで一つずつ取り出した個数と,totalメソッドの戻り値(階乗を用いた計算値)が一致する.
- どの文字列も,その中の文字をソートすれば,同じになる.すなわち,"wakayama" も "yamakawa" も "wkymaaaa" も,文字ソートで "aaaakmwy" になる.
- 順に生成する文字列において,どの連続する2つの文字列についても,前者が後者よりも辞書順で小さい.
連続する2つの文字列がどうなっているかを見たければ,
if c > 1 and !(s_last < s) return "NG" end
のところを
if c > 1 puts "#{s_last}:#{s}" if !(s_last < s) return "NG" end end
にするといいでしょう.
実行時間は,手元のマシンで「ruby permutation4.rb takehiko」を実行したところ,36秒ほどでした.
順列プログラミングはこれでおしまいです.と思ったけど,気が向いたらCで書きます.再帰なしでも比較的すっきりと記述できそうなのですが.