6面ダイスn個振ったときの合計がrになる組み合わせを求める

大中小のサイコロを投げる時、目の和が16になるの場合って何通りで... - Yahoo!知恵袋

a+b+c＝16かつa≦b≦cとする。
16≦3cよりc＝6
a+b＝10より10≦2bよりb＝5,6
∴(a,b,c)＝(5,5,6)(4,6,6)
それぞれ3通りで6通り。

abc＝18かつ1≦a≦b≦c≦6とする。
a^3≦18よりa＝1,2
①a＝1のときbc＝18
(a,b,c)＝(1,3,6)→6通り
②a＝2のときbc＝9
(a,b,c)＝(2,3,3)→3通り

めっちゃ頭いいな。

一般化してみる

• m番目のダイスをD[m]と表す
• D[m]≦D[m+1] かつ 1≦D[x]≦6
• D[n]は (r/n) ≦ 6 の組み合わせになる
• D[n]の各組み合わせについて D[n-1]は D[n-1]≦D[n] かつ (r-D[n]/n-1)≦D[n]を満たす
• 以下D[1]まで計算し組み合わせを求める

コードにしてみる

    const diceCombination = function(dices,sum,diceMustSmallerThan=6){
        if (sum/dices > 6) return [[]];
        if (dices == 1) {
            return [[sum]];
        }
        const res = [];
        const values = [1, 2, 3, 4, 5, 6].filter(p => p >= sum / dices && p <= diceMustSmallerThan);
        for (var v of values){
            if (sum - v <1) continue;
            diceCombination(dices-1,sum - v,v).forEach(ar=>{
                res.push([...ar,v]);
            })
        }
        return res;
    }

• ダイスの出目は[1, 2, 3, 4, 5, 6]と固定で持ちながらfilterにかける。
• filterは (r/n)を表すsum / dicesと D[m+1]以下をチェックするp <= diceMustSmallerThan
• これでD[x]の組み合わせが出るので dices=>dices-1 と sum=>sum-D[x] diceMustSmallerThan =D[x]として再帰させる
• 戻ってきた組み合わせにD[x]を追加して戻り配列に足しておく
• すべての出目について処理しが終われば戻る

結果

緑枠が出目の組み合わせ

3個で合計12

4個で合計20

5個で合計20

やったぜ。