显示所有爆炸骰子的组合

Question

我试图评估不同单位在桌面游戏(Mantic's Deadzone，对任何感兴趣的人)使用爆炸八边骰子(D8)的有效性。例如，播放机滚动3D8；对于显示8的每一个模具，允许播放机滚动一个额外的D8，并且可以无限地继续这样做。

作为一名数学家，我决定采用一种蛮力方法，并在C#中创建了一个递归函数，该函数编写了所有可能的骰子组合(最多有一定数量的附加骰子- -由max_generations变量-表示，在此之后，概率变得太小而不显着)。

    class Program
    {
        private int dice_faces = 8;
        private int max_generations = 5;

        static void Main(string[] args)
        {
            new Program().GenerateRoll(new List<int>() { 1 });
        }
        private List<int> GenerateRoll(List<int> dice)
        {
            if (dice == null || dice.Count == 0) 
                return new List<int>();

            if (dice[dice.Count - 1] == dice_faces)
            {
                if (dice.Count < max_generations)
                {
                    dice.Add(1);
                }
                else
                {
                    Console.WriteLine(string.Join(" ", dice));
                    dice = null;
                }
            }
            else
            {
                Console.WriteLine(string.Join(" ", dice));
                dice[dice.Count - 1]++;
            }

            return GenerateRoll(dice);
        }
    }

这个函数在以一个骰子开始时工作得很好，如上面的示例所示，但是它在以多个骰子开始时不会生成所有可能的滚动(即new Program().GenerateRoll(new List<int>() { 1, 1, 1 }););它只显示列表中最后一个骰子的滚动)。

如能协助更新该职能，以便与任何数目的起始骰子一起工作，我将不胜感激。

编辑以包括预期输出示例(显示几代爆炸骰子)

2 dice, 3 faces, 4 generations

1 G1, 1 G1
1 G1, 2 G1
1 G1, 3 G1, 1 G2
1 G1, 3 G1, 2 G2
1 G1, 3 G1, 3 G2, 1 G3
1 G1, 3 G1, 3 G2, 2 G3
1 G1, 3 G1, 3 G2, 3 G3, 1 G4
1 G1, 3 G1, 3 G2, 3 G3, 2 G4
1 G1, 3 G1, 3 G2, 3 G3, 3 G4 # max generation reached
2 G1, 1 G1
2 G1, 2 G1
2 G1, 3 G1, 1 G2
2 G1, 3 G1, 2 G2
2 G1, 3 G1, 3 G2, 1 G3
2 G1, 3 G1, 3 G2, 2 G3
2 G1, 3 G1, 3 G2, 3 G3, 1 G4
2 G1, 3 G1, 3 G2, 3 G3, 2 G4
2 G1, 3 G1, 3 G2, 3 G3, 3 G4 # max generation reached
3 G1, 1 G1, 1 G2
3 G1, 1 G1, 2 G2
3 G1, 1 G1, 3 G2, 1 G3
3 G1, 1 G1, 3 G2, 2 G3
3 G1, 1 G1, 3 G2, 3 G3, 1 G4
3 G1, 1 G1, 3 G2, 3 G3, 2 G4
3 G1, 1 G1, 3 G2, 3 G3, 3 G4 # max generation reached
3 G1, 2 G1, 1 G2
3 G1, 2 G1, 2 G2
3 G1, 2 G1, 3 G2, 1 G3
3 G1, 2 G1, 3 G2, 2 G3
3 G1, 2 G1, 3 G2, 3 G3, 1 G4
3 G1, 2 G1, 3 G2, 3 G3, 2 G4
3 G1, 2 G1, 3 G2, 3 G3, 3 G4 # max generation reached
3 G1, 3 G1, 1 G2, 1 G2
3 G1, 3 G1, 1 G2, 2 G2
3 G1, 3 G1, 1 G2, 3 G2, 1 G3
3 G1, 3 G1, 1 G2, 3 G2, 2 G3
3 G1, 3 G1, 1 G2, 3 G2, 3 G3, 1 G4
3 G1, 3 G1, 1 G2, 3 G2, 3 G3, 2 G4
3 G1, 3 G1, 1 G2, 3 G2, 3 G3, 3 G4 # max generation reached
3 G1, 3 G1, 2 G2, 1 G2
3 G1, 3 G1, 2 G2, 2 G2
3 G1, 3 G1, 2 G2, 3 G2, 1 G3
3 G1, 3 G1, 2 G2, 3 G2, 2 G3
3 G1, 3 G1, 2 G2, 3 G2, 3 G3, 1 G4
3 G1, 3 G1, 2 G2, 3 G2, 3 G3, 2 G4
3 G1, 3 G1, 2 G2, 3 G2, 3 G3, 3 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 1 G3, 1 G3
3 G1, 3 G1, 3 G2, 3 G2, 1 G3, 2 G3
3 G1, 3 G1, 3 G2, 3 G2, 1 G3, 3 G3, 1 G4
3 G1, 3 G1, 3 G2, 3 G2, 1 G3, 3 G3, 2 G4
3 G1, 3 G1, 3 G2, 3 G2, 1 G3, 3 G3, 3 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 2 G3, 1 G3
3 G1, 3 G1, 3 G2, 3 G2, 2 G3, 2 G3
3 G1, 3 G1, 3 G2, 3 G2, 2 G3, 3 G3, 1 G4
3 G1, 3 G1, 3 G2, 3 G2, 2 G3, 3 G3, 2 G4
3 G1, 3 G1, 3 G2, 3 G2, 2 G3, 3 G3, 3 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 1 G3, 1 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 1 G3, 2 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 1 G3, 3 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 2 G3, 1 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 2 G3, 2 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 2 G3, 3 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 1 G4, 1 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 1 G4, 2 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 1 G4, 3 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 2 G4, 1 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 2 G4, 2 G4
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 2 G4, 3 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 3 G4, 1 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 3 G4, 2 G4 # max generation reached
3 G1, 3 G1, 3 G2, 3 G2, 3 G3, 3 G3, 3 G4, 3 G4 # max generation reached

Answer 1

为了减少这个问题，我们将让所有可能的骰子卷用

0 (只滚动一个)到faces ^ dies - 1 (滚动所有八条)。例如，两个8边的模具(0到63)。

然后，我们只需将每一个编码转换为faces的一个新基(8基用于8边模)。

IEnumerable<int[]> GenerateRoll(int dies, int dice_faces)
{
    var allFaces = Enumerable.Range(1, dice_faces).ToArray();
    var allOnes = Enumerable.Repeat(1, dies);

    var count = (int)Math.Pow(dice_faces, dies);

    return
        Enumerable.Range(0, count)
        .Select(roll => ToBaseX(roll, dice_faces, allFaces, allOnes.ToArray()));                    
}

int[] ToBaseX(long value, int baseValue, int[] target, int[] buffer)
{
    var i = buffer.Length;

    do
    {
        buffer[--i] = target[value % baseValue];
        value = value / baseValue;
    }
    while (value > 0);

    return buffer;
}

嗯，那也不算太糟。现在，如果我们想要爆炸模具，我们选择生成一个新的滚动序列，为每一个爆炸模具辊( Where条件)。

IEnumerable<(int gen, int value)[]> GenerateRoll(int dies, int faces, int max_generations, int gen = 1)
{
    if (max_generations == gen)
        return Enumerable.Empty<(int, int)[]>();

    var allFaces = Enumerable.Range(1, faces).ToArray();
    var allOnes = Enumerable.Repeat(1, dies);

    return
         Enumerable.Range(0, (int)Math.Pow(faces, dies))
        .Select(roll => ToBaseX(roll, faces, allFaces, allOnes.ToArray()))
        .Select(roll => roll.Select(value => (gen, value)).ToArray())
        .SelectMany(roll =>
        {
            var explosions = roll.Count(r => r.value == faces);

            if (explosions == 0)
                return new[] { roll };

            return GenerateRoll(explosions, faces, max_generations, gen + 1) //roll explosion dies
                   .Select(last => roll.Concat(last).ToArray()); //the new roll gets appended to the streak
        });
}

测试程序

static void Main(string[] args)
{
    foreach (var roll in new Program().GenerateRoll(dies: 2, faces: 3, max_generations: 4))
    {
        Console.WriteLine(String.Join(", ", roll.Select(v => $"G{v.gen} {v.value}")));
    }

    Console.ReadKey();
}

输出

G1 1, G1 1
G1 1, G1 2
G1 1, G1 3, G2 1
G1 1, G1 3, G2 2
G1 1, G1 3, G2 3, G3 1
G1 1, G1 3, G2 3, G3 2
G1 2, G1 1
G1 2, G1 2
G1 2, G1 3, G2 1
G1 2, G1 3, G2 2
G1 2, G1 3, G2 3, G3 1
G1 2, G1 3, G2 3, G3 2
G1 3, G1 1, G2 1
G1 3, G1 1, G2 2
G1 3, G1 1, G2 3, G3 1
G1 3, G1 1, G2 3, G3 2
G1 3, G1 2, G2 1
G1 3, G1 2, G2 2
G1 3, G1 2, G2 3, G3 1
G1 3, G1 2, G2 3, G3 2
G1 3, G1 3, G2 1, G2 1
G1 3, G1 3, G2 1, G2 2
G1 3, G1 3, G2 1, G2 3, G3 1
G1 3, G1 3, G2 1, G2 3, G3 2
G1 3, G1 3, G2 2, G2 1
G1 3, G1 3, G2 2, G2 2
G1 3, G1 3, G2 2, G2 3, G3 1
G1 3, G1 3, G2 2, G2 3, G3 2
G1 3, G1 3, G2 3, G2 1, G3 1
G1 3, G1 3, G2 3, G2 1, G3 2
G1 3, G1 3, G2 3, G2 2, G3 1
G1 3, G1 3, G2 3, G2 2, G3 2
G1 3, G1 3, G2 3, G2 3, G3 1, G3 1
G1 3, G1 3, G2 3, G2 3, G3 1, G3 2
G1 3, G1 3, G2 3, G2 3, G3 2, G3 1
G1 3, G1 3, G2 3, G2 3, G3 2, G3 2

Answer 2

好吧，让我们从没有爆炸的发电机开始，这很容易：

private static IEnumerable<int[]> Generator(int faces, int count) {
  int[] state = Enumerable.Repeat(1, count).ToArray();

  do {
    yield return state.ToArray(); // safety : let's return a copy of state

    for (int i = state.Length - 1; i >= 0; --i)
      if (state[i] == faces)
        state[i] = 1;
      else {
        state[i] += 1;

        break;
      }
  }
  while (!state.All(item => item == 1));
}

现在，让我们使用上面的生成器来创建带爆炸的生成器：

private static IEnumerable<int[]> Generator(int faces, int count, int extra) {
  IEnumerable<(int[], int)> agenda = Generator(faces, count)
    .Select(state => (state, 0));

  for (bool hasWork = true; hasWork; ) {
    hasWork = false;
    List<(int[], int)> next = new List<(int[], int)>();

    foreach (var state in agenda) {
      int explosions = Math.Min(
        state.Item1.Skip(state.Item2).Count(item => item == faces),
        extra - state.Item1.Length + count);

      if (explosions <= 0)
        yield return state.Item1;
      else 
        foreach (var newState in 
          Generator(faces, explosions).Select(adds => state.Item1.Concat(adds)))
            next.Add((newState.ToArray(), state.Item1.Length));
    }

    agenda = next;
    hasWork = next.Count > 0;
  }
}

演示：

// 2 dice (3 faces each) with at most 4 explosions (extra dice) allowed
var results = string.Join(Environment.NewLine, Generator(3, 2, 4) 
  .Select(item => string.Join(", ", item)));

Console.Write(results);

结果：

1, 1          # No explosion
1, 2
2, 1
2, 2
1, 3, 1       # last 3 exploded 
1, 3, 2
2, 3, 1
2, 3, 2
3, 1, 1       # first 3 exploded
3, 1, 2
3, 2, 1
3, 2, 2
3, 3, 1, 1    # both first and last 3 exploded
3, 3, 1, 2
3, 3, 2, 1
3, 3, 2, 2
1, 3, 3, 1    # last 3 exploded, we have 3 which we exploded again
1, 3, 3, 2
2, 3, 3, 1
2, 3, 3, 2
3, 1, 3, 1    # first 3 exploded, we have 3 which we exploded again
3, 1, 3, 2
3, 2, 3, 1
3, 2, 3, 2
3, 3, 1, 3, 1 # both first and last 3 exploded, we have 3 which we exploded again
3, 3, 1, 3, 2
3, 3, 2, 3, 1
3, 3, 2, 3, 2
3, 3, 3, 1, 1
3, 3, 3, 1, 2
3, 3, 3, 2, 1
3, 3, 3, 2, 2
3, 3, 3, 3, 1, 1
3, 3, 3, 3, 1, 2
3, 3, 3, 3, 1, 3
3, 3, 3, 3, 2, 1
3, 3, 3, 3, 2, 2
3, 3, 3, 3, 2, 3
3, 3, 3, 3, 3, 1
3, 3, 3, 3, 3, 2
3, 3, 3, 3, 3, 3
1, 3, 3, 3, 1
1, 3, 3, 3, 2
2, 3, 3, 3, 1
2, 3, 3, 3, 2
3, 1, 3, 3, 1
3, 1, 3, 3, 2
3, 2, 3, 3, 1
3, 2, 3, 3, 2
3, 3, 1, 3, 3, 1
3, 3, 1, 3, 3, 2
3, 3, 1, 3, 3, 3
3, 3, 2, 3, 3, 1
3, 3, 2, 3, 3, 2
3, 3, 2, 3, 3, 3
3, 3, 3, 1, 3, 1
3, 3, 3, 1, 3, 2
3, 3, 3, 1, 3, 3
3, 3, 3, 2, 3, 1
3, 3, 3, 2, 3, 2
3, 3, 3, 2, 3, 3
1, 3, 3, 3, 3, 1
1, 3, 3, 3, 3, 2
1, 3, 3, 3, 3, 3
2, 3, 3, 3, 3, 1
2, 3, 3, 3, 3, 2
2, 3, 3, 3, 3, 3
3, 1, 3, 3, 3, 1
3, 1, 3, 3, 3, 2
3, 1, 3, 3, 3, 3
3, 2, 3, 3, 3, 1
3, 2, 3, 3, 3, 2
3, 2, 3, 3, 3, 3

编辑：如果您想获取/跟踪代(或爆炸)，您可以实现额外的方法：

private static int[] Explosions(int[] record, int faces, int count) {
  int[] result = new int[record.Length];

  int extra = count;
  int startAt = count;
  int completed = 0;
  int generation = 0;

  while (true) {
    generation += 1;
    int take = extra;

    extra = record
      .Skip(completed)
      .Take(take)
      .Count(item => item == faces);

    if (extra <= 0)
      break;

    for (int i = 0; i < extra; ++i)
      if (startAt + i >= result.Length)
        return result;
      else
        result[startAt + i] = generation;

    startAt += extra;
    completed += take;
  }

  return result;      
}

让我们有一些可读的文本：

private static String Explain(int[] record, int faces, int count) {
  return string.Join(" then ", record
    .Zip(Explosions(record, faces, count), (item, rank) => new { item, rank})
    .GroupBy(value => value.rank, value => value.item)
    .Select(group => $"explosion #{group.Key} ({string.Join(", ", group)})"));
}

演示：

Console.WriteLine(string.Join(", ", 
  new int[] { 3, 3, 3, 3, 1, 3, 2 })); 
// We have 2 dice with 3 faces each;
// We want to explain 3, 3, 3, 3, 1, 3, 2 sequence
Console.WriteLine(string.Join(", ", Explosions(
  new int[] { 3, 3, 3, 3, 1, 3, 2 }, 3, 2)));
Console.WriteLine();
Console.Write(Explain(new int[] { 3, 3, 3, 3, 1, 3, 2 }, 3, 2));

结果：

3, 3, 3, 3, 1, 3, 2 # Initial serie
0, 0, 1, 1, 2, 2, 3 # Corresponding explosions (generations)

explosion #0 (3, 3) then explosion #1 (3, 3) then explosion #2 (1, 3) then explosion #3 (2) 

编辑2:最后，如果您想限制的不是extra骰子，而是generations (0 -仅限初始投，最多是1爆炸，不管它是什么骰子等等)：

private static IEnumerable<int[]> Generator(int faces, int count, int generations) {
  IEnumerable<(int[], int, int)> agenda = Generator(faces, count)
    .Select(state => (state, 0, 0));

  for (bool hasWork = true; hasWork;) {
    hasWork = false;
    List<(int[], int, int)> next = new List<(int[], int, int)>();

    foreach (var state in agenda) {
      int explosions = state.Item1.Skip(state.Item2).Count(item => item == faces);

      if (explosions <= 0 || state.Item3 >= generations)
        yield return state.Item1;
      else
        foreach (var newState in
          Generator(faces, explosions).Select(adds => state.Item1.Concat(adds)))
            next.Add((newState.ToArray(), state.Item1.Length, state.Item3 + 1));
    }

    agenda = next;
    hasWork = next.Count > 0;
  }
}