Counting up "broadly": Not 0,1,2,..,9,10,11,..,99 but 00, 01, 10, 11, 02, 12, 20, 21, 22, 03, .., 99

Question

When a counter is made up from a fixed number of digits (2 in the title), standard counting-up works by incrementing from the least to the most significant digit and upon overflow reset it.

I want to count differently: A 4 digit number in base-10 would be counted up in base-2 until the overflow back to 0000 would happen, but instead the base is increased to base-3 while omitting previously counted numbers, so only continue with 0002, 0012, 0020, 0021, 0022, 0102, 0112, 0120, 0121, 0122, 0200, 0201, 0202, 0210, 0211, ...^(fixed!) and all other numbers with at least one 2 in in. Upon 2222 the switch to base-4 happens, so all 4-digit combinations with at least one 3 in it follow. In the end all numbers from 0000 to 9999 are in this sequence, but in a different ordering.

This way a 9 would not should up anywhere until the last 10% of the sequence.

How would such a counter be implemented in theory (without the naive digit-presence¹ check)? Can I easily jump to the n-th element of this ordering or count backwards? And is there an actual name instead of "broad counting" for it?

1: A "naive digit-presence check" would count up to base-2, and when switching to base-3 all generated numbers are checked to ensure that at least on 2 is in them. Upon switching to base 4 (i.e. the 2222-0003 step) all numbers must contain at least one 3. So after 2222 the numbers 0000, 0001, 0002 are omitted because they lack a 3 and thus have been enumerated before. And so on, base-N means the digit N-1 has to be present at least once.

Answer 1

So first you want all numbers with the digits 0 in order. i.e. just 00

Then all numbers with the digits 0,1: 00, 01, 10, 11 but excluding 00

Then all numbers with digits 0,1,2: 00, 01, 02, 10, 11, 12, 20, 21, 22 but excluding 00, 01, 10, 11 i.e. all those which does not have a digit 2.

It is simplist to implement by going through all combinations and excluding those which have already been printed.

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

To understand the theory of how this works you can arrange the 2 digit version in a grid

 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

Note how each set of numbers form "shells". In the first shell we have just one number, the first and second shell have 4 = 2^2 numbers, the first, second and third shells have 9 = 3^2 numbers etc.

We can use this to work out how many numbers in each shell. In the two digit case is 1^2=1, 2^2-1^2=3, 3^2-2^2=5, 4^2-3^2=7.

With three digits its cubes instead. 1^3=1, 2^3-1^3=9-1 = 8, 3^3-2^3=27-9 = 18, etc.

With four digits its forth powers.

By considering the shells we could work out a more efficient way of doing things. In the 3 digit case we have shells of cubes, and would need to work out the path through the shell. I'm not sure if there is much to be gained unless you have a large number of digits.

To get the order for this consider the 3 digit case and let x,y,z be the digits in order. If we are looking at the k-th shell, we want to get all the solutions on the three planes x=k, y=k, z=k. These solutions split into those with x

In pseudocode

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

It should be possible to generalise this to d-dimension. Let our coordinates here be x1, x2, ..., xd. The solution in the k-th shell will lie on the (d-1)-dimensional hyperplanes x1=k, x2=k, ..., xd=k. Again we loop through x1=0, to x1=k-1, with x1=0 the problem is the same as the d-1 dimensional problem which suggests a recursive approach.

  // 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,"");
 }