わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

順列プログラムの動作確認(3)

順列プログラムの動作確認(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で書きます.再帰なしでも比較的すっきりと記述できそうなのですが.