Show all the combinations of exploding dice

Question

I am trying to evaluate the effectiveness of different units in a tabletop game (Mantic's Deadzone, for anyone who is interested) that uses exploding eight-sided dice (D8). For example, a player rolls 3D8; for each die that shows an 8, the player is allowed to roll an additional D8, and can continue to do so ad infinity.

Not being a mathematician, I decided on a brute-force approach, and have created a recursive function in C# that writes all the possible combinations of dice rolls (up to a certain number of additional dice - represented by the max_generations variable -, after which the probabilities become too small to be significant).

    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);
        }
    }

This function works well when starting with a single dice as in the example above, but it does not generate the full range of possible rolls when starting with multiple dice (i.e. new Program().GenerateRoll(new List<int>() { 1, 1, 1 });); it only shows the rolls for the last dice in the list.

I would be grateful for any assistance with updating the function to work with any number of starting dice.

edited to include sample expected output (showing generations of exploding dice)

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

Well, let's start from the generator without explosion, it's quite easy:

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));
}

Now, let's use the generator above to create the generator with explosion:

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;
  }
}

Demo:

// 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);

Outcome:

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

Edit: If you want to get / track generations (or explosions) you can implement extra methods:

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;      
}

Let's have some readable text:

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)})"));
}

Demo:

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));

Outcome:

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) 

Edit 2: Finally, if you want to restrict not extra dice, but generations (0 - initial cast only, at most 1 explosion whatever dice it is etc.):

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;
  }
}

Answer 2

To reduce the problem, we will have all possible dice rolls be represented by an encoding from

0 (roll only ones) to faces ^ dies - 1 (roll all eights). E.g., for two 8-sided dies (0 to 63).

We then just convert every encoded to a new base of faces (base 8 for 8-sided dies)

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;
}

Well, that wasn't too bad. Now if we want exploding dies, we choose to generate a new roll sequence of 1 die roll for every exploding die present (the Where condition)

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
        });
}

Test program

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();
}

Output

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