0
給定n個骰子每個都有x個邊，我試圖枚舉所有可能的抽籤。例如，如果我們有10個三面骰子，並且它們全都落在值1側：
我有一個啓發式方法（EnumerateDrawsH），它只適用於預定義數量的邊和遞歸方法（EnumerateDrawsR）適用於任何數量的邊。目前，我的版本R的性能遠低於H. 在R中，我需要一種高效的方式來保持寫入繪圖中骰子總數的軌跡，這應該是sum參數，但它是不正確的。我找到的唯一解決方法是重做遞歸的每個級別上的總數，並將其存儲在drawSum局部變量中，該變量經過測試以結束遞歸。有誰知道如何獲得sum參數中的正確值？列舉所有可能的抽牌投擲X個面對骰子的N個
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
static class EnumerateDicesDraws
{
public static void Run()
{
int nbDices = 10;
Stopwatch watch;
watch = Stopwatch.StartNew();
EnumerateDicesDraws.EnumerateDrawsH(nbDices);
watch.Stop();
Console.WriteLine(watch.Elapsed);
watch = Stopwatch.StartNew();
EnumerateDicesDraws.EnumerateDrawsR(nbDices, 3);
watch.Stop();
Console.WriteLine(watch.Elapsed);
Console.ReadKey(true);
}
public static void EnumerateDrawsR(int nbDices, int nbSides)
{
string filePath = Path.Combine(Path.GetTempPath(), string.Concat("Draws[R]", nbDices, ".txt"));
int[] dices = new int[nbSides];
using (StreamWriter writer = new StreamWriter(filePath, false))
EnumerateDrawsR(0, 0, nbDices, dices, writer);
}
private static void EnumerateDrawsR(int index, int sum, int nbDices, int[] dices, StreamWriter writer)
{
int drawSum = 0;
for (int i = 0; i < dices.Length; i++)
{
drawSum += dices[i];
if (drawSum == nbDices)
{
for (int j = 0; j < dices.Length - 1; j++)
writer.Write(string.Format("{0:D2} ", dices[j]));
writer.Write(string.Format("{0:D2} ", dices[dices.Length - 1]));
writer.Write(string.Format("{0:D3}", sum));
writer.WriteLine();
for (; index < dices.Length; index++)
dices[index] = 0;
return;
}
}
/*
if (sum == nbDices)
{
for (int j = 0; j < dices.Length; j++)
writer.Write(string.Format("{0:D2} ", dices[j], j < dices.Length - 1 ? " " : null));
writer.WriteLine();
for (; index < dices.Length; index++)
dices[index] = 0;
return;
}
*/
if (index < dices.Length)
{
EnumerateDrawsR(index + 1, sum + dices[index], nbDices, dices, writer);
EnumerateDrawsR(index, sum + ++dices[index], nbDices, dices, writer);
}
}
public static void EnumerateDrawsH(int nbDices)
{
StringBuilder draws = new StringBuilder();
string format = "{0:D2} {1:D2} {2:D2}\r\n";
int cumul = 0;
int[] dices = new int[3];
for (dices[0] = 0; dices[0] <= nbDices; dices[0]++)
{
cumul = dices[0];
if (cumul == nbDices)
{
for (int i = 1; i < dices.Length; i++)
dices[i] = 0;
draws.AppendFormat(format, dices[0], dices[1], dices[2]);
break;
}
for (dices[1] = 0; dices[1] <= nbDices; dices[1]++)
{
cumul = dices[0] + dices[1];
if (cumul == nbDices)
{
for (int i = 2; i < dices.Length; i++)
dices[i] = 0;
draws.AppendFormat(format, dices[0], dices[1], dices[2]);
break;
}
for (dices[2] = 0; dices[2] <= nbDices; dices[2]++)
{
cumul = dices[0] + dices[1] + dices[2];
if (cumul == nbDices)
{
draws.AppendFormat(format, dices[0], dices[1], dices[2]);
break;
}
}
}
}
File.WriteAllText(Path.Combine(Path.GetTempPath(), string.Concat("Draws[H]", nbDices, ".txt")), draws.ToString());
}
}
EDIT
她是由nlucaroni建議的解決方案，具有固定的遞歸退出條件。
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
static class Programm
{
static void Main()
{
var watch = Stopwatch.StartNew();
var outputFile = DiceRoll.Draws(nbDicesTotal: 10, nbValues: 6);
watch.Stop();
Console.WriteLine(watch.Elapsed);
Console.WriteLine();
Console.WriteLine("Output to :");
Console.WriteLine(outputFile);
Console.ReadKey(true);
}
}
static class DiceRoll
{
/// <summary>
/// Writes all possible draws (or distributions) for a given number of dices having a given number of values
/// </summary>
/// <param name="nbDicesTotal">Total number of dices rolled</param>
/// <param name="nbValues">Number of different values of each dice</param>
/// <returns>Output file path in system temporary folder</returns>
public static string Draws(int nbDicesTotal, int nbValues)
{
var filePath = Path.Combine(Path.GetTempPath(), string.Format("DiceDraws[{0}].txt", nbDicesTotal));
var distribution = new int[nbValues];
using (var writer = new StreamWriter(filePath, false))
foreach (var draw in Draws(0, 0, nbDicesTotal, distribution))
//Call to Select method adds huge cost of performance. Remove call to Select to compare.
writer.WriteLine(string.Join(" ", draw.Select(x => x.ToString("D2"))));
return filePath;
}
/// <summary>
/// Returns all possible draws (or distributions) for a given number of dices having a given number of values
/// </summary>
/// <param name="distributionIndex">We are incrementing the number of dices of this value</param>
/// <param name="nbAddedDices">Number of dices (up to nbDicesTotal) considered in the recursion. EXIT CONDITION OF THE RECURSION</param>
/// <param name="nbDicesTotal">Total number of dices rolled</param>
/// <param name="distribution">Distribution of dice values in a draw. Index is dice value. Value is the number of dices of value 'index'</param>
/// <returns>All possible draws</returns>
/// <remarks>Recursive methode. Should not be called directly, only from the other overload</remarks>
static IEnumerable<IEnumerable<int>> Draws(int distributionIndex,
int nbAddedDices,
int nbDicesTotal,
int[] distribution)
{
// Uncomment for exactness check
// System.Diagnostics.Debug.Assert(distribution.Sum() == nbAddedDices);
if (nbAddedDices == nbDicesTotal)
{
yield return distribution;
nbAddedDices -= distribution.Length - distributionIndex;
for (; distributionIndex < distribution.Length; distributionIndex++)
distribution[distributionIndex] = 0;
}
if (distributionIndex < distribution.Length)
{
foreach (var draw in Draws(distributionIndex + 1, nbAddedDices, nbDicesTotal, distribution))
yield return draw;
distribution[distributionIndex]++;
foreach (var draw in Draws(distributionIndex, nbAddedDices + 1, nbDicesTotal, distribution))
yield return draw;
}
}
}
試着把它想成3^10的選擇。這很容易計算。然後只計算該值（減1）並將每個值轉換爲基數3.每個基數3位數是一個模（減1）的值。 （你有沒有多餘的三面骰子？我無法想象它。） – HABO