Dice combinations to a total

Question

Trying to find a nice algorithm for working out d4 dice combinations for a total. For example 3 dice with four sides, all the combinations to make 4 would give: 004 013 112 022

I will be using c# but python or pseudo would be great. Just need some help for the algorithm. Would always be a four sided die but total and number of dice would be parameters.

Any ideas would be great. Thank you.

Answer 1

Here's a tweak to trincot's answer that doesn't require the creation of intermediate lists, and which computes a minimum value for the current dice, resulting in less wasted calls (.Net Fiddle).

public static ArrayList combos(int nDice, int tot, int max)
{
    var res = new ArrayList();
    combos(res, "", nDice, tot, max);
    return res;
}

private static void combos(ArrayList res, String sol, int nDice, int tot, int max)
{
    if(tot == 0)
    {
        res.Add(sol);
        return;
    }
    
    for(int side = 1+(tot-1)/nDice; side <= Math.Min(tot, max); side++)
        combos(res, sol+side, nDice-1, tot-side, side);
}

Test:

public static void Main (string[] args) {
    int nDice = 3;
    int nFaces = 4;
    for(int tot=1; tot<=nDice*nFaces+1; tot++)
    {
        Console.WriteLine ("\nTot: " + tot);
        foreach (var combo in combos(nDice, tot, nFaces)) {
            Console.WriteLine (combo);
        }
    }
}

Output:

tot: 1
1

tot: 2
11
2

tot: 3
111
21
3

tot: 4
211
22
31
4

tot: 5
221
311
32
41

tot: 6
222
321
33
411
42

tot: 7
322
331
421
43

tot: 8
332
422
431
44

tot: 9
333
432
441

tot: 10
433
442

tot: 11
443

tot: 12
444

tot: 13

Answer 2

You can use recursion.

For instance, in Python it would look like this:

def combis(num_dice, target, minval=1):
    if target == 0:
        return [""]  # solution
    if num_dice < 1 or target < 0:
        return [] # no solution

    res = []
    for side in range(minval, min(5, target + 1)):
        for combi in combis(num_dice - 1, target - side, side):
            res.append(str(side) + combi)
    return res
    
print(combis(3, 4))

If really this had to be done in Python, then one would use a library like itertools.

The output is a list of strings, where each character in a string is a digit representing the side of a die. The strings are never longer than the first argument (num_dice), but they can be shorter, meaning fewer dice are involved. You could pad those with "0" if desired.

Implementation in C#

using System;
using System.Collections;

class MainClass {
    public static ArrayList combis(int numDice, int target, int minval=1) {
        var res = new ArrayList();
        if (target == 0) {
            res.Add(""); // solution
        } else if (numDice > 0 && target > 0) {
            for (int side = minval; side < 5 && side <= target; side++) {
                foreach (var combi in combis(numDice - 1, target - side, side)) {
                    res.Add(side.ToString() + combi);
                }
            }
        }
        return res;
    }

    public static void Main (string[] args) {
        // Example run
        foreach (var combi in combis(3, 4)) {
            Console.WriteLine (combi);
        }
    }
}