骰子组合总和

Question

试图找到一个很好的算法来计算 d4 骰子组合的总数。例如 3 个骰子有四个面，组成 4 的所有组合将给出：004 013 112 022

我将使用 c#，但 python 或伪代码会很棒。只需要一些算法的帮助。始终是四面骰子，但骰子总数和数量将是参数。

任何想法都会很棒。谢谢。

Answer 1

你可以使用递归。

例如，在 Python 中它看起来像这样：

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))

如果真的必须在 Python 中完成，那么人们会使用像 itertools.

这样的库

输出是一个字符串列表，其中字符串中的每个字符都是代表骰子面的数字。字符串永远不会长于第一个参数 (num_dice)，但它们可以更短，这意味着涉及的骰子更少。如果需要，您可以用“0”填充它们。

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);
        }
    }
}

Answer 2

这是对 trincot 的 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);
}

测试：

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);
        }
    }
}

输出：

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

骰子组合总和

Dice combinations to a total

algorithm

die

dice

C# 中的实现