什么是最好的方法来设计递归函数，产生所有的N位数字的组合？

Question

作为我大学算法课程的一部分，我们必须设计一个递归函数来生成所有n位数的组合。

112

113

121

221

222

223

322

323

331

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

我非常感谢你能提供的任何帮助

Answer 1

归纳地思考：你如何把用[1..n]中的数字生成所有n位数的问题分解成一个较小的实例，再加上一点更多的工作？也许最明显的是将所有可能的数字加到递归生成的所有(n-1)位数字的前面。我将使用C（但C++类似）在缓冲区中一次累积一个数字。

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

称之为：

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

在int中构建数字也很好。代码略短，但它将int分解成字符串的工作留给了printf，因此从某种意义上说，这是双重工作：

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

print_all(0, 0, n);

正如我在评论中指出的，用更难理解的递归代替明显的循环应用程序是不明智的。但既然你问了，

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

并呼吁：

print_all(1, 0, 0, n);