What's the best way to design a recursive function that generates all combinations of n-digits numbers?

Question

As part of my Algorithms course in collegue, we have to design a recursive function that generates all combinations of n-digits numbers.

This is an example:

Sample input:

3

Sample output:

111

112

113

121

122

123

131

132

133

211

212

213

221

222

223

231

232

233

311

312

313

321

322

323

331

332

333

I would like to point out that I've already solved this problem, so that people won't comment that this is homework and I must do it on my own. Anyway, here is my code in C++ :

void S6_1(int r, int n, int p, int d)
{
    if (d == 0)
        return;
    S6_1(r, n, p, d - 1);
    r = r * 10 + d;
    if (p == 1)
        cout << r << endl;
    else
        S6_1(r, n, p - 1, n);
}

void S6(int n)
{
    S6_1(0, n, n, n);
}

The main reason I post this is the fact that I strongly believe that there must be another way to solve this problem.

I really appreciate any help you can provide

I strongly believe there must be another way to solve political conflicts than applying war. Give me a solution please. — πάντα ῥεῖ
Your output is incorrect. You're missing 131, 132, 133, 231, 232, 233. — Jim Mischel
If you have n digits, there are n^n n-digit numbers. Another way to think of the problem is counting from 0 to (n^n)-1, and converting each number to base-n. You can easily map 0 to 111, 1 to 112, etc. — Jim Mischel
Note that this can be solved iteratively without too much difficulty. After all, you can count to 1000 without using recursion. — Raymond Chen

Gene Gene · Accepted Answer · 2016-05-30T21:50:51

Think inductively: How do you separate the problem of generating all n-digit numbers with digits in [1..n] into a smaller instance of itself plus a little more work? Perhaps the most obvious is to tack all possible digits onto the front of all (n-1)-digit numbers that are recursively generated. I'll use C (but C++ is similar) to accumulate the numbers in a buffer one at a time.

// In buf[i..n-1], enumerate all numbers having n-i digits with values in [1..n]. 
void print_all(char *buf, int i, int n) {
  if (i == n) {               // Here n - i == 0, so we're done. Print.
    printf("%.*s\n", n, buf);
    return;
  }
  for (int digit = 1; digit <= n; ++digit) {
    buf[i] = digit + '0';     // put a digit at position i
    print_all(buf, i + 1, n); // recursively put the rest
  }
}

To call it:

char buf[n];
print_all(buf, 0, n);

It's also fine to build the number in an int as you did. The code is a bit shorter, but it leaves the job of decomposing the int into a string to printf, so in a sense it's double work:

void print_all(int b, int i, int n) {
  if (i == n) {
    printf("%d\n", b);
    return;
  }
  for (int digit = 1; digit <= n; ++digit) {
    print_all(10 * b + digit, i + 1, n);
  }
}

And to call it...

print_all(0, 0, n);

Edit

As I pointed out in comments, replacing obvious loop applications with recursion that's harder to understand is not smart. But since you asked,

// Enumerate all numbers formed by appending to the number in b all (n-i)-digit
// numbers starting with a digit in [d..n] and all other digits in [1..n].
void print_all(int d, int b, int i, int n) {
  if (d > n) return;
  if (i == n) {
    printf("%d\n", b);
    return;
  }
  print_all(1, 10 * b + d, i + 1, n); // enumerate all with more digits
  print_all(d + 1, b, i, n); // enumerate other values of i'th digit
}

And to call:

print_all(1, 0, 0, n);

What's the best way to design a recursive function that generates all combinations of n-digits numbers?

2 Answers