いきなりですが問題です．
http://d.hatena.ne.jp/takehikom/20080319/1205876284 で作ったプログラムの出力が正しいことを示しなさい．
辞書順ですべて出力されていることを示すには，以下があればいいでしょう．
- 総数が正しい．すなわち，順列の総数を求める - わさっき で求める数値と，順列を順番にすべて - わさっき で求める文字列の総数が一致する．
- どの文字列も，異なる．
- どの文字列も，その中の文字をソートすれば，同じになる．すなわち，"wakayama" も "yamakawa" も "wkymaaaa" も，文字ソートで "aaaakmwy" になる．
- 順に出力される文字列をソートしても，ソート前とソート後とで順序が変わらない．
それぞれを示すための方針を書いておきます．まず戦略として，「出力をリダイレクトして，標準的なUnixコマンド(外部コマンド)に通す」と「示すためのRubyコードを書き，順列生成プログラムと結合する」の2通りが考えられます．それと，作ったプログラムの
printf("%6d : %s\n", i + 1, str2)
は都合が悪いので，
puts str2
に置き換えておきます．
外部コマンドを使うなら，総数はwcで求められます．ソート前後で順序が変わらないのは，md5sumを使えばいいでしょう．ソートはもちろんsort．どの文字列も異なるのは，sortのあとにuniqですね．
しかし，外部コマンドを使う場合は，文字ソートで同じになることを示すのが容易ではありません．文字列を文字単位に分けるコマンド，あったかな…．
もう一つのやり方…Rubyで検証コードを書くなら，文字ソートは，「文字列.split(//u).sort.join('')」とすればおしまいです．
あと，「どの文字列も，異なる」と「ソート前とソート後とで順序が変わらない」の条件はくっつけて，次のようにできますね．残りの2つ(総数，文字ソート一致)が正しければ，等価な条件なはずです．
- 順に生成する文字列において，どの連続する2つの文字列についても，前者が後者よりも辞書順で小さい．
(2008-03-23 7:45ごろ追記) 外部コマンドで「文字ソート」についてですが，ここでソートは必須ではなく，もとの文字列の字が1回ずつ使われているのを確認すればいいことに気付きました．そうすると，例えば "wakayama" が入力のときは，出力の文字列一つ一つについて，「"w" を取り除く」「"a" を取り除く」…のようにして1文字ずつ取り除き，最終的に空文字列になればいいということです(出力の文字列の字数ば別途検査します)．もちろん，1文字を取り除くのは，sedでできます．
