math - 向上计数 "broadly": Not 0, 1,2,..,9,10,11,..,99 但 00, 01, 10, 11, 02, 12, 20, 21, 22, 03, .., 9

Question

当计数器由固定数量的数字(标题中的 2 个)组成时，标准计数的工作方式是从最低有效数字增加到最高有效数字，并在溢出时重置它。

我想以不同的方式计数:以 10 为基数的 4 位数字将以 2 为基数向上计数，直到溢出回到 0000会发生，但基数增加到基数 3 而 省略 以前计算过的数字，所以只继续 0002, 0012, 0020, 0021, 0022, 0102, 0112, 0120, 0121, 0122, 0200, 0201, 0202, 0210, 0211, ... (已修复!)和所有其他号码中至少有一个 2 英寸。在 2222 上切换到基数 4 发生了，因此所有 4 位数字组合至少包含一个 3。最后所有号码来自 0000至 9999都在这个序列中，但顺序不同。

这样，直到序列的最后 10% 之前，9 都不应该出现在任何位置。

理论上如何实现这样的计数器(没有天真的数字存在 1 检查)？我可以轻松跳转到此排序的第 n 个元素或向后计数吗？是否有一个实际名称而不是“广泛计算”？

1 :“天真的数字存在检查”将计数到基数 2，并且当切换到基数 3 时，将检查所有生成的数字以确保其中至少有 2。切换到基础时 4 (即 2222 - 0003 步骤)所有数字必须至少包含一个 3 .所以在2222之后数字 0000 , 0001 , 0002被省略，因为它们缺少 3，因此之前已被枚举。依此类推，base-N 意味着数字 N-1 必须至少出现一次。

Answer 1

因此，首先您需要按顺序排列所有数字为 0 的数字。即只有 00

然后所有数字为 0,1: 00, 01, 10, 11 但不包括 00

然后所有数字为 0,1,2 的数字:00, 01, 02, 10, 11, 12, 20, 21, 22 但不包括 00, 01, 10, 11 即所有那些没有数字 2 的数字。

通过遍历所有组合并排除那些已经打印的组合来实现是很简单的。

for(maxdigit=0; maxdigit<10; ++maxdigit) {
  for(digit1 = 0; digit1 <= maxdigit; ++digit1) { 
  for(digit2 = 0; digit2 <= maxdigit; ++digit2) { 
  for(digit3 = 0; digit3 <= maxdigit; ++digit3) { 
  for(digit4 = 0; digit4 <= maxdigit; ++digit4) { 
     if( digit1 < maxdigit && digit2 < maxdigit 
      && digit3 < maxdigit && digit4 < maxdigit) continue;
     print( digit1, digit2, digit3, digit4);
  }}}}
}

要了解其工作原理，您可以在网格中排列 2 位数字版本

 00 | 01 | 02 | 03 | 04
-----    |    |    |
 10   11 | 12 | 13 | 14
----------    |    |
 20   21   22 | 23 | 24
---------------    |
 30   31   32   33 | 34
--------------------
 40   41   42   43   44

请注意每组数字如何形成“ shell ”。在第一个 shell 中我们只有一个数字，第一个和第二个 shell 有 4 = 2^2 个数字，第一个、第二个和第三个 shell 有 9 = 3^2 个数字等等。

我们可以使用它来计算每个 shell 中有多少个数字。在两位数的情况下是 1^2=1, 2^2-1^2=3, 3^2-2^2=5, 4^2-3^2=7。

用三位数代替它的立方体。 1^3=1、2^3-1^3=9-1 = 8、3^3-2^3=27-9 = 18，以此类推。

用四位数字表示它的四次幂。

通过考虑 shell，我们可以找到一种更有效的做事方式。在 3 位数的情况下，我们有立方体 shell ，需要计算穿过 shell 的路径。除非你有大量的数字，否则我不确定是否有很多收获。

要获得此顺序，请考虑 3 位数字的情况，并让 x,y,z 成为按顺序排列的数字。如果我们查看第 k 个 shell ，我们希望得到 x=k、y=k、z=k 三个平面上的所有解。这些解决方案分为具有 x 的解决方案

在伪代码中

          for(shell=0;shell<=9;++shell) {
          // Do the L shaped part
          for(x=0;x<shell;++x) {
            // The the y-leg, which has z=k
            for(y=0;y<shell;++y)
                print(x,y,shell);
            // Do the z-leg, which has   y=k
            for(z=0;z<=shell;++z)
                print(x,shell,z);
          }
          // Now the x=shell face
          for(y=0;y<=shell;++y)
            for(z=0;z<=shell;++z)
                print(shell,y,z);
        }              

应该可以将其推广到 d 维。让我们这里的坐标为 x1, x2, ..., xd。第 k 个 shell 中的解将位于 (d-1) 维超平面 x1=k, x2=k, ..., xd=k 上。我们再次循环 x1=0，到 x1=k-1，当 x1=0 时，该问题与建议递归方法的 d-1 维问题相同。

  // solve the dim-dimensional problem for 
  // prefix the output with prefix
  function solve(int shell,int dim,String prefix) {
    if(dim==1) { 
        // only one solution with the last digit being the shell
        print(prefix+shell);
        return;
    }

    // loop through the first digit
    for(int x=0;x<shell;++x) {
        String prefix2 = prefix + x;
        solve(shell,dim-1,prefix2);
    }

    // Now to the x=k hypercube, 
    // need to do this in a separate recursion
    String prefix2 = prefix + shell;
    hypercube(shell,dim-1,prefix2);
}

// all solutions in dim dimensions with a given prefix
function hypercube(int shell,int dim,String prefix) {
    if(dim==1) {
        for(int x=0;x<=shell;++x)
            println(prefix+x);
    }
    else {
        for(int x=0;x<=shell;++x) {
            String prefix2 = prefix + x;
            hypercube(shell,dim-1,prefix2);
        } 
     }
 }

 // Now call, here we do the 4 digit version
 for(shell=0;shell<=9;++shell) {
          solve(shell,4,"");
 }