5

我想用 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

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

4

1 回答 1

3

只需计算和转换。我在这里写了一些应该对早期答案有所帮助的东西。

这应该是一个相对容易解决的问题。

本质上,您只是在计算字符串 集合Σ^5其中Σ = { 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();
        }
      };
    }
  };
}

...可以按如下方式使用:

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

基本上,我们生成区间[0, 3^5)中的数字,其中3是我们的基数,5是我们想要的字符串长度,然后将这些数字转换为三进制形式。0变成000003^5变成100000。您还必须注意不要使用太大的基数,否则结果String将包含错误的字符。


这里的解决方案是仅调用strings(n, n). 请注意,根据您的基数或所需数字长度的大小,您可能希望使用longor 甚至BigInteger.

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

如果基数小于Character.MIN_RADIX或大于Character.MAX_RADIX,则使用基数10代替。

您可以看到Character.MIN_RADIXis2MAX_RADIXis的值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 ...

于 2012-09-12T21:37:03.293 回答