Permutation

这是一道要求你用1~9这十个数字来构造三个三位数abc,def,ghi。使得abc是def的二分之一，同时是ghi的三分之一。打印出所有满足条件的三个三位数。
我先想到的是以下的法一：

#include <cstdio>

int main()
{
  for (int a = 1; a < 10; a++) {
    for (int b = 1; b < 10; b++) {
      for (int c = 1; c < 10; c++) {
        for (int d = 1; d < 10; d++) {
         for (int e = 1; e < 10; e++) {
           for (int f = 1; f < 10; f++) {
            for (int g = 1; g < 10; g++) {
              for (int h = 1; h < 10; h++) {
                if (b != a && c != a && c != b && d != a && d != b && d != c && e != a && e != b && e != c && e != d && f != a && f != b && f != c && f != d && f != e && g != a && g != b && g != c && g != d && g != e && g != f && h != a && h != b && h != c && h != d && h != e && h != f && h != g) {
                  int i = 45-a-b-c-d-e-f-g-h;
                  int sum1 = 100*a + 10 * b + c, sum2 = 100 * d + 10 * e + f, sum3 = 100 * g + 10 * h + i;
                  if (2 * sum1 == sum2 && 3 * sum1 == sum3)
                   printf("%d %d %d\n", sum1, sum2, sum3);
                }
              }
            }
          }
        }
      }
    }
  }
  return 0;
}

但是这个程序有一个明显的问题就是速度太慢，整个程序运行了0.368ms因为这是在所有循环之后再判断是否成立（即有没有数重复使用）,这样就会浪费很多次循环，其次三个三位数的首位：a、d、g是可以有更明确的范围限定的，因为假如a超过了3，那么ghi一定大于1000了。还有就是我一开始把循环写成了形如for (int i = 1; i < 10; && i != j; i++) 而这种写法其实是错误的，因为本来这样写都主旨在于对i != j 所有其它情况进行循环，但假如这样写的话，i只会循环到最大的i使得i<j。这样就会有很多情况讨论不到。
所以我之后就写了以下的代码：

#include <cstdio>

int main()
{
  for (int a = 1; a < 4; a++) {
    for (int b = 1; b < 10; b++) {
      if (b == a)
        continue;
      for (int c = 1; c < 10; c++) {
        if (c == a || c == b)
          continue;
        for (int d = 2; d < 7; d++) {
          if (d == a || d == b || d == c)
            continue;
          for (int e = 1; e < 10; e++) {
            if (e == a || e == b || e == c || e == d)
              continue;
            for (int f = 1; f < 10; f++) {
              if (f == a || f == b || f == c || f == d || f == e)
                continue;
              for (int g = 3; g < 10; g++) {
                if (g == a || g == b || g == c || g == d || g == e || g == f)
                  continue;
                for (int h = 1; h < 10; h++) {
                  if (h == a || h == b || h == c || h == d || h == e || h == f || h == g)
                    continue;
                  int i = 45-a-b-c-d-e-f-g-h;
                  int x = 100 * a + 10 * b + c, y = 100 * d + 10 * e + f, z = 100 * g + 10 * h + i;
                  if (2 * x == y && 3 * x == z)
                    printf("%d %d %d\n", x, y, z);
                }
              }
          }
        }
      }
    }
  }
  return 0;
}

这样子，速度一下字就增加到0.08ms了，这比之前的速度快了整整46倍！但是，我经过反思，又觉得循环还能减少到三个，以下就是这种方法的代码：

#include <cstdio>

int main()
{
  for (int a = 1; a < 4; a++) {
    for (int b = 1; b < 10; b++) {
      if (b == a)
        continue;
      for (int c = 1; c < 10; c++) {
        if (c == a || c == b)
          continue;
        int x = 100 * a + 10 * b + c;
        int y = 2 * x, z = 3 * x;
        if (z > 987)
          break;
        int digits[10] = {0}, ok = 1;
        digits[0] = digits[a] = digits[b] = digits[c] = 1;
        while (y != 0 && z != 0) {
          int i = y % 10, j = z % 10;
          if (i == j || digits[i] || digits[j]) {
            ok = 0;
            break;
          }
          y /= 10;
          z /= 10;
          digits[i] = digits[j] = 1;
        }
        if (ok)
          printf("%d %d %d\n", x, 2 * x, 3 * x);
      }
    }
  }
  return 0;
}

而这种方法的速度已经增快到0.01ms了。有些人可能会不明白一维数组digits的作用是什么，我就在此解释一下吧。digits赋值为以的位置表示这个位置上的数字已被占用，比如digits[1] == 1表示数字一已经被使用了。而while循环里的if判断的意义是看i和j是不是相等，并看digits中的第i个与第j个是否为0，以判断有没有重复数字使用。
以下是法四，供参考：

#include <cstdio>

void get_next_digit(int digits[], int numbers[])
{
    int total = 0;
    for (int i = 1; i < 10; i++)
        total += digits[i];

    // full
    if (total == 8) {
        total = 0;
        for (int i = 0; i < 8; i++)
            total += numbers[i];
        int x = numbers[0]*100 + numbers[1]*10 + numbers[2];
        int y = numbers[3]*100 + numbers[4]*10 + numbers[5];
        int z = numbers[6]*100 + numbers[7]*10 + 45 - total;
        if (2*x == y && 3*x == z)
            printf("%d %d %d\n", x, y, z);
        return;
    }

    // not full yet
    for (int i = 1; i < 10; i++) {
        if (digits[i])
            continue;
        digits[i] = 1;
        numbers[total] = i;
        get_next_digit(digits, numbers);
        digits[i] = 0;
        numbers[total] = 0;
    }
}

int main()
{
#ifndef CON_IO
    freopen("permutation.in", "r", stdin);
    freopen("permutation.out", "w", stdout);
#endif
    int digits[10] = {0}, numbers[9] = {0};
    digits[0] = 1;
    get_next_digit(digits, numbers);
    return 0;
}