リストの上限と下限を上手く算出しようって寸法さ。
補足1
「a桁とb桁の積はa+b桁かa+b-1桁なのですべて集めて9個になるには2*(a+b)=9 か 2*(a+b)-1=9 だが後者しかなくて a+b = 5、積の方は4(=5-1)桁」
むむっ…まずはこれを読み解く。
a桁とb桁の積はa+b桁かa+b-1桁、というのは確かにその通りだった。
(この辺は数学知識として基本なのかな…)
2桁*2桁の場合、 下限は 10*10=100, 上限は 99*99=9801 で、2桁+2桁=4桁か2桁+2桁-1=3桁かのいずれか。
今回、パンデジタル数として9桁の数字を作りたいが、その条件を満たすのは、
乗算に使用するa桁とb桁、積のa+b桁またはa+b-1桁が9になる事、つまり 2*(a+b)=9 か 2*(a+b)-1=9。
奇数にならないといけないので、-1している後者しかこの式が成り立たない。
ここまでで、乗算に使用するa桁とb桁の合計が5桁、積が4桁に限定される。
これを前提に、割られる数yの上限と下限を割る数xから特定して無駄な組み合わせでの計算を省くようにしたのがこちら。
multiplyLimit
メソッドで、上限と下限を出している。> multiplyLimit 1 (1000,9999) > multiplyLimit 10 (100,999) > multiplyLimit 100 (10,99) > multiplyLimit 1000 (1,9)
補足2
multiplyLimit
メソッドの呼び出しをリスト内包表記の中で毎回ではなく、1~4の場合の上限・下限を算出してArrayに持たせておき、
桁数を配列のインデックスとして参照するようにしてみた。
> multiplyLimit array (1,4) [(1,(1000,9999)),(2,(100,999)),(3,(10,99)),(4,(1,9))]これが効率的かどうかは悩ましいが、やるなら
Data.Array
使えば実現できそう、とパッと思いついて実際書き換えも上手くいったのは、過去の問題で使った経験が活きたように思う。
また、前回のバージョンから、
foldl1 (++) . map show
を>>= show
と書き換えてみた。補足3
こちらのコメントを参考に、上限と下限を桁数ではなく下限 1234/x 上限 9876/x で算出したのがこちら。また、
sort $ >>= show
をsort $ concatMap show ns
と書き換えてみた。