わさっきhb

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

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

順列プログラムの動作確認(1) - わさっきについて,標準的なUnixコマンドを使った場合の答えを書いておきます.
出力は「puts str2」で行うように書き換えたRubyファイルを,p.rb としています.

総数が正しい

$ ruby p.rb ABCD | wc
     24      24     120
$ ruby permutation_count.rb ABCD
ABCD: 24
$ ruby p.rb takehiko | wc
  20160   20160  181440
$ ruby permutation_count.rb takehiko
takehiko: 20160

permutation_count.rb とは,順列の総数を求める - わさっき にあるプログラムのことです.

元の文字列を並べ替えたものとなっている

$ ruby p.rb ABCD | sed -e 's/A/_/;s/B/_/;s/C/_/;s/D/_/' | uniq | wc
      1       1       5
$ ruby p.rb takehiko | sed -e 's/t/_/;s/a/_/;s/k/_/;s/e/_/;s/h/_/;s/i/_/;s/k/_/;s/o/_/' | uniq | wc
      1       1       9

最初の「1 1 5」は,wcは1行だけを受け取ったということです.これは「____」です.改行コードを加えて,5バイト.ということで,「ruby p.rb 文字列」の出力の各行から,元の文字列の文字を1文字ずつ見つけて「_」に置き換えていくと,どの行も「____」になることで,元の文字列の文字を1個ずつ使っているのが確認できました.
ところで,sedコマンドの指示で「's/A/_/;s/B/_/;s/C/_/;s/D/_/'」がすっきりしませんが,文字列の各文字が異なっていれば

$ ruby p.rb ABCD | sed -e 's/[ABCD]/_/g' | uniq | wc
      1       1       5

でいいものの,重複文字があると,例えば

$ ruby p.rb AACD | sed -e 's/[AACD]/_/g' | uniq | wc
      1       1       5
$ ruby p.rb ACCD | sed -e 's/[AACD]/_/g' | uniq | wc 
      1       1       5

という喜ばしくない結果になります.「sed -e 's/[AACD]/_/g'」は「sed -e 's/[ACD]/_/g'」と同じ意味になることに注意すると,このコマンドが検証方法として不適切なのが分かりますね.

どの生成文字列も異なる

辞書順になっている

上の二つは,独立した要件です.というのも,単に「辞書順になっている」だと,生成文字列1≦生成文字列2≦… でもいいわけです.もちろんこの順列生成問題で要求されているのは,生成文字列1<生成文字列2<… でして,等号を消すには,「どの文字列も異なる」ことを抑えないといけない,となります.
しかし実行コマンドとしては,二つを同時に確認するのでいいでしょう.

$ ruby p.rb ABCD | md5sum
165ebf68318cfd5f103c6f20290a1def *-
$ ruby p.rb ABCD | sort | uniq | md5sum
165ebf68318cfd5f103c6f20290a1def *-
$ ruby p.rb takehiko | md5sum
1147b23ff3ecfd3b8a3cbff4613a32ba *-
$ ruby p.rb takehiko | sort | uniq | md5sum
1147b23ff3ecfd3b8a3cbff4613a32ba *-