Given n dices each one having x sides, I am trying to enumerate all the possibles draws.
For instance, if we have 10 three sided dices, and all of them fall on the value 1 side :
10 00 00
I have an heuristic method (EnumerateDrawsH) that works only for a pre-definied number of sides and a recursive method (EnumerateDrawsR) that works for any number of sides. For now, my version of R is much less performant than H.
In R, I need an efficent way of keeping the track of the total number of dices in the draw being written, which should be the sum parameter, but it is incorrect. The only workaround I have found yet is to redo the total on each level of the recursion and store it in the drawSum local variable, which is tested to end the recursion. Does anyone know how to get the correct value in the sum parameter ?
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
Her is the solution suggested by nlucaroni, with the recursion exit condition fixed.
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;
}
}
}
You can enumerate all draws by counting in base x with n digits.
For example, initiate all dice in the array to the lowest value, let's say the dice are labeled from 0 to (x-1). Then, you start with an array of 0's, this is the first and lowest value, then you can increase the the right most until it equals x-1, where you increase the second dice, reset the first dice, and proceed, et cetera.
The Art of Computer Programming Volume 4: Fascicle 3 has a ton of information if you need to enumerate them in a certain order.