java - 打印所有非零数字按升序排列的数字

Question

我正在尝试编写一个程序，该程序将一些数字和一个基数作为参数，并通过具有升序的非零数字的数字向上计数。例如，以 4 为基数的 3 位数字，它应该打印:

000 001 002 003 010 011 012 013 020 022 023 030 033 100 101 102 103 110 111 112 113 120 122 123 130 133 200 202 203 220 222 223 230 233 300 303 330 333

在 base 3 中，它应该打印 4 位数字:

0000 0001 0002 0010 0011 0012 0020 0022 0100 0101 0102 0110 0111 0112 0120 0122 0200 0202 0220 0222 1000 1001 1002 1010 1011 1012 1020 1022 1100 1101 1102 1110 1111 1112 1120 1122 1200 1202 1220 1222 2000 2002 2020 2022 2200 2202 2220 2222

我成功地做到了这一点，但我的算法似乎不必要地复杂且耗时(时间对我的应用程序非常重要)。如果无法提高速度，是否有任何方法可以使其更快或简化它？

程序如下:

public static void count(int base, int size)
{
    int[] array = new int[size];
    print(array); // private print method prints out the array
    int index = 0;
    while (index < array.length)
    {
        if (array[index] < base - 1)
        {
            // check whether we need to increase array[index] by extra to maintain the order
            if (array[index] == 0)
            {
                int i;
                // search for the next nonzero digit
                // this search seems to take unnecessary time; is there a faster alternative?
                for (i = index + 1; i < array.length && array[i] == 0; i++);

                // check whether there was, in fact, some later nonzero digit
                if (i < array.length) array[index] = array[i];
                else                  array[index] = 1;
            }

            else array[index]++;

            print(array);
            index = 0;
        }

        // carry over to the next digit
        else array[index++] = 0;
    }
}

Answer 1

我会选择递归解决方案:

public static void count(int base, int size) {
    int[] configuration = new int[size];
    placeDigits(configuration, base, 0, 1);
}

public static void placeDigits(int[] configuration, int base, int pos, int minNonZero) {
    if (pos >= configuration.length) {
        print(configuration);
    } else {
        // 0 is a possible candidate
        configuration[pos] = 0;
        placeDigits(configuration, base, pos + 1, minNonZero);
        // digits between minNonZero and base
        for (int d = minNonZero; d < base; d++) {
            configuration[pos] = d;
            placeDigits(configuration, base, pos + 1, d);
        }
    }
}

它将数字一个接一个地放入数组中，并遵守非零数字必须不递减的约束。