java - 在 Java 中以 2、3、4 等为基数计数并输出所有排列

Question

我想用 Java 编写一个函数，它将一个整数作为输入，并输出直到该整数的所有可能的数字排列。例如:

f(1)

0

f(2) 应该输出:

00 01 10 11

f(3) 应该输出:

000 001 002 010 011 012 020 021 022 100 .... 220 221 222

也就是说，它应该输出数字 0、1、2 的所有 27 个数字排列。

f(4) 应该输出 0000 0001 0002 0003 0010 ... 3330 3331 3332 3333

f(5) 应该输出 00000 00001 ... 44443 44444

我一直在尝试解决这个问题，但似乎无法弄清楚如何去做，并且一直对我需要多少循环感到困惑。有谁知道如何解决这个问题？提前致谢。

Answer 1

只需计算并转换。我写了一些应该有助于早期回答的东西 here .

This should be a relatively easy problem to solve.

Essentially, you're merely computing the set of strings Σ^5 where Σ = { 0, 1, 2 }.

static Iterable<String> strings(final int radix, final int digits) {
  return new Iterable<String>() {

    public Iterator<String> iterator() {
      return new Iterator<String>() {

        private final String pad;
        {
          final StringBuilder buf = new StringBuilder(digits);
          for (int n = digits; n >= 0; --n) {
            buf.append('0');
          }
          pad = buf.toString();
        }

        private final int hi = (int) Math.pow(radix, digits);
        private int cursor;

        public boolean hasNext() {
          return cursor < hi;
        }

        public String next() {
          final String rsl = Integer.toString(cursor++, radix);
          return pad.substring(0, digits - rsl.length()) + rsl;
        }

        public void remove() {
          throw new UnsupportedOperationException();
        }
      };
    }
  };
}

... which can be used as follows:

for (final String val : strings(3, 5)) {
  System.out.println(val);
}

Basically, we generate the numbers in the interval [0, 3^5), where 3 is our radix and 5 our desired string length, and then convert the numbers into ternary form. 0 becomes 00000, 3^5 becomes 100000. You must also take care to not use too large a radix, otherwise the resulting String will contain bad characters.

---

此处的解决方案是仅调用 strings(n, n)。请注意，根据您的基数或所需的数字长度有多大，您可能希望改用 long 甚至 BigInteger。

另外，因为它依赖于 Integer.toString , 请确保您记住以下警告...

If the radix is smaller than Character.MIN_RADIX or larger than Character.MAX_RADIX, then the radix 10 is used instead.

您可以看到 Character.MIN_RADIX 的值是 2 和 MAX_RADIX是 36。如果您使用此范围之外的基数，它将默认为 10...您将需要使用数字的自定义扩展字符集编写自己的转换。这样一个itoa函数的一般形式如下:

    private static final char[] ALPHABET = { '0', '1', '2', '3', ... };

    public static String itoa(int value, final int radix, int width) {
      final char[] buf = new char[width];
      while (width > 0) {
        buf[--width] = ALPHABET[value % radix];
        value /= radix;
      }
      return new String(buf);
    }

---

下面是您使用的工作示例(查看 ideone 上的结果)。

static Iterable<String> f(final int n) {
  return strings(n, n);
}

public static void main(final String[] argv) {
  for (int n = 1; n <= 5; ++n) {
    for (final String string : f(n)) {
      System.out.printf("%s ", string);
    }
    System.out.println();
  }
}

...产生:

0

00 01 10 11

000 001 002 010 011 012 020 021 022 100 101 102 110 111 ...

0000 0001 0002 0003 0010 0011 0012 0013 0020 0021 0022 0023 0030 ...

00000 00001 00002 00003 00004 00010 00011 00012 00013 00014 00020 00021 00022 ...