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

Question

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

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

以4位数字为基数的3应该打印：

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

如果您不介意将数字保存在内存中，您可以编写以下算法：

1. 从数字 0，1...基数-1 开始
2. 对于每个添加的数字，d，首先添加零，然后以数字d或更高的数字开头的所有先前数字（通过起始数字和位数索引这些数字，您可以直接访问它们）。

或者，就像一些人喜欢说的那样，dpstyle:让dp[i][j]用 数字和最左边的数字 dp[i][j]=[d]映射（d）dp[l][k]，对于所有l

（我从Haskell那里借用了，它通常意味着连接列表）。

例如，基数为4，3位数:

Start with one digit:
0,1,2,3

Add to the second digit from the first sequence:
10,11,12,13
20,22,23
30,33

Third digit, add from all previous sequences:
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

JavaScript代码：

var base = 4;

var dp = [,[]];

for (var j=0; j<base; j++){
  dp[1][j] = [j];
}

for (var i=2; i<4; i++){
  dp[i] = [];
  for (var j=1; j<base; j++){
    var d = j * Math.pow(10,i - 1);
    dp[i][j] = [d];
    for (var l=1; l<i; l++){
      for (var k=j; k<base; k++){
        dp[i][j] = dp[i][j].concat(
                     dp[l][k].map(function(x){
                       return d + x;
                     }));
      }
    }
  }
}

console.log(JSON.stringify(dp))

/*
 [null,[[0],[1],[2],[3]]
,[null,[10,11,12,13]
,[20,22,23]
,[30,33]]
,[null,[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]]]
*/

Answer 2

好吧，这有点作弊，但这里有一个用伪代码表示的解决方案：

results : list
for i in 1..max
   if '0' not in str(i)
       append i to results
   fi
rof
print results

另一方面，这是作弊吗？“非零数字的数字”本质上是一个关于数字的十进制表示的问题，而不是某种意义上的数字本身。

时间复杂度当然是O（n）——至少将str（i）计算为一个步骤，这有点作弊。

只是为了好玩，这是Python中的相同解决方案：

print [i for i in xrange(max) if '0' not in str(i)]

以及递归解决方案的草图:

设< code>dig是非零数字的列表，即< code>['1 '，' 2 '，' 3 '，' 4 '，' 5 '，' 6 '，' 7 '，' 8 '，' 9']。枚举长度列表中所有字符串< code>ceil(log10(max))(小问题，为什么有这个限制？).

按顺序打印这些字符串，当超过max时停止。

Answer 3

我会选择递归解决方案:

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

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