寻求无需转置矩阵处理骰子掷骰集合的优化方法

Great question—dealing with discard-the-extremes dice mechanics without getting crushed by exponential growth (like that brutal 6^n problem) is a super common headache for anyone working with dice probability systems. The good news is you absolutely don’t need to enumerate every possible roll or mess with transpose matrices. Let’s break down two practical, scalable approaches:

1. Dynamic Programming (DP) with State Tracking #

The core idea here is to track aggregated states instead of individual rolls as you build up your dice pool. Instead of storing every possible sequence of rolls, you store counts of how many ways you can reach a given combination of:

• Total sum of the dice pool so far
• Minimum value in the pool so far
• Maximum value in the pool so far

Step-by-Step Breakdown #

• Base Case: Start with a single die. For a d6, your initial state is a simple array/dictionary where dp[value] = 1 for values 1 through 6 (each face has exactly 1 way to occur).
• Build Up the Pool: For each additional die, update your DP state by combining the existing state with the new die’s possible values. For every existing state (current_sum, current_min, current_max) with count count, and every possible die face v:
  • New sum: current_sum + v
  • New min: min(current_min, v)
  • New max: max(current_max, v)
  • Add count to the new state’s total count.
• Calculate Adjusted Sums: Once you’ve built the full state for n dice, compute the adjusted sum for each state as total_sum - current_min - current_max. Aggregate counts across all states that result in the same adjusted sum, then divide by 6^n to get probabilities.

Why This Works #

Instead of the exponential 6^n operations needed to enumerate all rolls, this approach runs in polynomial time: for n dice, the total number of states is roughly n * 6 * 6 * (6n) (since sum ranges from n to 6n, min/max each range from 1 to 6). For n=10, that’s ~21,600 states—way better than the 60 million individual rolls you’d have to process otherwise.

Pseudocode Example

# Initialize for 1 die
dp = {}
for v in range(1, 7):
    dp[(v, v, v)] = 1  # (sum, min, max) -> count

# Add remaining n-1 dice
for _ in range(n-1):
    new_dp = {}
    for (sum_, min_, max_), count in dp.items():
        for v in range(1, 7):
            new_sum = sum_ + v
            new_min = min(min_, v)
            new_max = max(max_, v)
            key = (new_sum, new_min, new_max)
            new_dp[key] = new_dp.get(key, 0) + count
    dp = new_dp

# Calculate adjusted sums and probabilities
adjusted_counts = {}
total_rolls = 6 ** n
for (sum_, min_, max_), count in dp.items():
    adjusted_sum = sum_ - min_ - max_
    adjusted_counts[adjusted_sum] = adjusted_counts.get(adjusted_sum, 0) + count

probabilities = {k: v / total_rolls for k, v in adjusted_counts.items()}

2. Inclusion-Exclusion with Generating Functions #

If you prefer a more math-focused approach, generating functions paired with inclusion-exclusion can work equally well. Here’s the gist:

• The generating function for a single d6 is f(x) = x + x² + x³ + x⁴ + x⁵ + x⁶.
• To count rolls where the min is exactly m and max is exactly M, use inclusion-exclusion:
  • Total rolls with all dice between m and M: (x^m + x^{m+1} + ... + x^M)^n
  • Subtract rolls where all dice are ≥ m+1 and ≤ M (no ms)
  • Subtract rolls where all dice are ≥ m and ≤ M-1 (no Ms)
  • Add back rolls where all dice are ≥ m+1 and ≤ M-1 (subtracted twice)
• For each valid m ≤ M, extract the coefficients of x^T in the resulting polynomial (these represent the number of ways to get total sum T with min m and max M). The adjusted sum is T - m - M, so you can map these coefficients to the corresponding adjusted sum counts.

This approach is great if you’re comfortable with polynomial arithmetic, and it also scales polynomially instead of exponentially.

Final Takeaway #

You don’t need to brute-force every possible roll or rely on transpose matrices. Both DP state tracking and inclusion-exclusion with generating functions let you compute adjusted sums and their probabilities efficiently, even for larger dice pools where 6^n becomes completely unmanageable.

内容的提问来源于stack exchange，提问作者Krivand