比較関数の自然な例(2)

VBA

昨日の VBAHaskellの紹介 その12 では、5つある問題のうち5番目だけを対象にした。今考えると、元記事 「1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に」 にある問題4

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。 

が、2015年4月20日のブログ 比較関数の自然な例 で探していたものだということに気付いた。

VBAHaskellで実装しているソート関数 sortIndex_pred は、比較関数を第2引数に与えることで任意の大小関係でソートを実行できるのだが、たいていの場合はそんなもの使わなくても、何らかの変換写像でマップした値に通常の大小関係を適用すればできてしまう。

しかしこの問題4はそういうやり方では難しく、以下のような比較関数が必要になる。

Function Question4Comp(ByRef a As Variant, ByRef b As Variant) As Variant
    Question4Comp = IIf(val(a & b) < val(b & a), 1, 0)
End Function

例えば "5" と "53" では、文字列としての通常の大小関係は "5" < "53" だが、この順に連結した時と逆順に連結した時の比較をしてみると "553" > "535" なので、"53" < "5" というわけである。この問題を解くには、この大小関係で数字を大きい順に並べる必要がある。

この比較関数があればイミディエイト・ウィンドウ上で片付けられる。

' 1～99 の整数乱数を10個作る
a = mapF(p_getCLng(p_rnd(,99)), repeat(0,10))
' 文字列化する
b = mapF(p_cStr, a)
' 件の比較関数でソート（逆順）
c = subM(b, reverse(sortIndex_pred(b,p_Question4Comp)))
' もとの数列を出力
printM a
  11  99  67  2  57  10  10  79  28  5
' ソート後の列を出力
printM c
  99  79  67  57  5  28  2  11  10  10
' 文字列を結合して表示
? foldl1(p_plus, c)
997967575282111010

ただし文字列化関数 p_str は今日必要性に気付いて Haskell_2_stdFun.bas に追加したものだ。