2
\$\begingroup\$

I wrote a program in c what looks for integer solutions of different formulas. The program asks the user for a dimension which defines the formula. For example, the formula of the third dimension has three variables, the formula of the second dimension has two variables. The formulas look similar to the following:

dim     formula
2       a + b
3       a + b + c
4       a + b + c + d

and so on. Next step, the program asks the user for a maximum value of all the variables. For a given dimension, 3 for instance, the code could look like:

for(int a = 1; a <= max; a++)
{
    for(int b = 1; b <= max; b++)
    {
        for(int c = 1; c <= max; c++)
        {
            do_sth();
        }
    }
}

Of course, this would be a bad algorithm. It checks each possible combination up to 6 times, just in different order. The better alternative would be:

for(int a = 1; a <= max; a++)
{
    for(int b = 1; b <= a; b++)
    {
        for(int c = 1; c <= b; c++)
        {
            do_sth();
        }
    }
}

To make that work for all dimensions, I had to find a way to stack multiple loops depending on the users input. I wrote a recursive loop function:

int number[100];
int dim, max;

void loop(int depth)
{
    for(number[depth] = 1; number[depth] <= number[depth-1]; number[depth]++)
    {
        if(depth == dim - 1)
        {
            do_sth();
        }
        else
        {
            loop(depth+1);
        }
    }
}

int main(void)
{
    printf("Enter a dimension: ");
    scanf("%d", &dim);
    printf("Enter a maximum value: ");
    scanf("%d", &max);
    for(number[0] = 1; number[0] <= max; number[0]++)
    {
        loop(1);
    }
}

Notes:

  • It is not important, what do_sth() does. It builds the actual formula I don't want to show here.
  • To be able to calculate the runtime, I wrote a program what calculates the number of combinations to try. I posted it on this question.

My code works fine but I would like to know if there's a better way to do this.

\$\endgroup\$
3
\$\begingroup\$

Can be done without recursion

You can do the same thing without recursion, by simply adding one to the rightmost dimension, and then "carrying over" when that number exceeds the one to its left.

Here is a sample implementation:

void loop()
{
    int i = 0;

    for (i = 0; i < dim; i++) {
        number[i] = 1;
    }
    do {
        do_sth();
        for (i = dim - 1; i > 0; i--) {
            if (number[i] < number[i-1]) {
                number[i]++;
                break;
            }
            number[i] = 1;
        }
        if (i == 0) {
            if (number[0] < max) {
                number[i]++;
            } else {
                return;
            }
        }
    } while (1);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.