それぞれ x 面を持つ n 個のサイコロが与えられた場合、考えられるすべてのドローを列挙しようとしています。たとえば、10 個の 3 面サイコロがあり、それらすべてが値 1 側にある場合:
10 00 00
事前に定義された面の数に対してのみ機能する発見的方法 (EnumerateDrawsH) と再帰的方法 (EnumerateDrawsR ）任意の数の側面で機能します。今のところ、私のバージョンの R は H よりもパフォーマンスがはるかに劣っています。R では、書き込み中のドローのサイコロの総数を追跡する効率的な方法が必要です。これは sum パラメーターである必要がありますが、それは正しくありません。私が見つけた唯一の回避策は、再帰の各レベルで合計をやり直して、再帰を終了するためにテストされる drawSum ローカル変数に格納することです。sum パラメータで正しい値を取得する方法を知っている人はいますか?
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());
}
}
編集
彼女は 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;
}
}
}