hlhhs11 / customer-arrangement-optimization Goto Github PK

組み合わせ生成関数で、特に何も考えずnCr=nCn-rに従ってr>n/2のときnCn-rに変換してたけど、そうすると得られるイテレータにまで影響が及んでしまう。

たとえば5C4に対応するイテレータが欲しいとなったら
[1,2,3,4],[1,2,3,5][1,2,4,5],[1,3,4,5],[2,3,4,5]
が欲しい、ということになるが、0114現在でのプログラムでは、rをn-rに変換して
[1],[2],[3],[4]
を出力してしまう。

でもかといってnCr=nCn-rの性質を使わないのももったいないので、もしr>n/2となったときには'r=n-rとしてイテレータを作った上で、最後に"n個の数字"から"出力結果に入っている数字"だけを取り出す'という形で作り直したい。(5C4の例なら、一旦[1],[2],[3],[4]をつくったうえで、最後に[1,2,3,4,5]から各数字を抜いた配列を作る

組み合わせはn!/r!(n-r)!で表されることからわかるように、オーダーはほぼ階乗といっていい。たとえば96C26を計算サイトで計算すると、2.052799757E+23とでてくる。組み合わせの単純な数値でさえこの大きさなのだから、そこでイテレータを生成しようとしたらとてつもなく長い時間がかかるのは目に見えている。

ということで、全通りの配置図を検証する方式は現実的に無理。
抽象度を上げてもっと楽に計算できる方法を探したい