Need help for find the logic of a heuristic sequence

I'm developing a system that can explore entirely a simple heuristic map of this gender (which can have different numbers of branches, and different depths) :

Simple heuristic map

So, I'm saving the positions explored in an int array of the size of the depth of the map. The goal is to explore all nodes of the map, so to have this output : 0 2 6, 0 2 7, 0 3 8, 0 3 9, 1 4 10 etc.. But actually with my code (which needs to be called several times because it can update just one time the array), i have this : 0 2 6, 0 2 7, 0 3 8, **1** 3 9, 1 4 10 etc..

This is my code, I don't know how to solve this problem..

void get_next_branch(int *s, int nbr_branch, int size)
{
    int a;

    a = 0;

    while (a < size)
    {
        condition = (size - a)/(nbr_branch - 1);
        if (condition)
        {
            if (s[size - 1] % (condition) + 1 == condition)
                s[a]++;
        }
        a++;
    }
}

And this is the main example who call this function.

int main(void)
{
    int id[3] = {0, 2, 6};

    while (id[2] < 13)
    {
        printf("%d %d %d\n", id[0], id[1], id[2]);
        get_next_branch(id, 2, 3);
    }

    return (0);
}

I thank you in advance!

Solution

You might want to use a closed formula for this problem

b being the number of branches
d the depth you want to find the numbers in (d >= 0)

we get immediately

Number of nodes at depth d = b^d+1

(since at depth 0 we have already two nodes, there is no "root" node used).

The number of the first node at depth d is the sum of the number of nodes of the lower levels. Basically,

first node number at depth 0 = 0

first node number at depth d > 0 = b¹ + b² + b³ + ... + b^d

This is the sum of a geometric series having a ratio of b. Thanks to the formula (Wolfram)

first node number at depth d = b * (1 - b^d) / (1 - b)

E.g. with b == 2 and d == 2 (3^rd level)

Number of nodes: 2 ^ 3 = 8

Starting at number: 2 * (1 - 2^2) / (1 - 2) = 6

A program to show the tree at any level can be done from the formulas above.

To print a number of levels of a tree with b branches:

Utility power function

int power(int n, int e) {
   if (e < 1) return 1;
   int p=n;
   while (--e) p *= n;
   return p;
}

The two formulas above

int nodes_at_depth(int branches, int depth) {
   return power(branches, depth+1);
}

int first_at_depth(int branches, int depth) {
    return (branches * (1 - power(branches, depth))) / (1 - branches);
}

Sample main program, to be called

./heuristic  nb_of_branches  nb_of_levels

that calls the two functions

int main(int argc, char **argv)
{
   if (argc != 3) return 1;

   int b = atoi(*++argv);
   int d = atoi(*++argv);

   if (b < 2) return 2;

   int i,j;
   for (i=0 ; i<d ; i++) {
      int n = nodes_at_depth(b, i);  // number of nodes at level i
      int s = first_at_depth(b, i);  // first number at that level
      for (j=0 ; j<n ; j++) printf(" %d", s+j);
      printf("\n");
   }

   return 0;
}

Calling

./heuristic 2 4

gives

 0 1
 2 3 4 5
 6 7 8 9 10 11 12 13
 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29