Print all numbers whose nonzero digits are in ascending order

Question

I'm trying to write a program which takes as arguments a number of digits and a base, and counts upward through the numbers that have their nonzero digits in ascending order. For instance, in base 4 with 3 digits, it should print:

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

and in base 3 with 4 digits it should print:

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

I have done this successfully, but my algorithm seems unnecessarily complicated and time-consuming (time is very important for my application). Is there any way of either making it faster, or simplifying it if the speed cannot be improved?

Here is the program:

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

I would go for a recursive solution:

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

It places digits one after the other into the array and observes the constraint that the non-zero digits must be non decreasing.

Answer 2

Okay, this is a bit of a cheat, but here's a solution expressed in pseudocode:

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

On the other hand, is it a cheat? "numbers with nonzero digits" is inherently a question about the decimal representation of the numbers, not in some sense the numbers themselves.

Time complexity is O(n) of course -- at least counting str(i) as a single step, which is where it is a little bit of a cheat.

Just for fun, here's the same solution in Python:

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

And a sketch of a recursive solution:

Let dig be a list of the nonzero digits, i.e., ['1','2','3','4','5','6','7','8','9']. Enumerate all strings on that list of length ceil(log10(max)) (quiz question, why that limit?).

Print those strings in order, stopping when max is exceeded.

Answer 3

If you don't mind keeping the numbers in memory, you could code the following algorithm:

1. Start with the numbers 0,1...base-1
2. For each added digit, d, first add zero, then all previous numbers that begin with digits d or higher (indexing those by starting digit and number of digits, you could access them directly).

Or, as some like to phrase, dp style: Let dp[i][j] represent the sequence of numbers with i digits and left-most digit j. Then dp[i][j] = [d] ++ map (d +) dp[l][k], for all l < i and k >= j, where d = j * 10 ^ (i - 1)

(I borrowed the ++ from Haskell, where it often means to concat lists).

For example, base 4, 3 digits:

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 code:

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 4

Quite an interesting program you have written.

I've tried to increase the performance of the nested search, but so far I haven't found a way to make the worst-case scenario of searching for the next nonzero digit less than O(n).

In the worst-case scenario, the subarray A[i..array.length-1] is not sorted, and array[i] = 0,therefore to find the next non-zero digit, you have to do a linear search.

Aditionally, if there is no next non-zero digit, you have to search the whole array to "find it".

(For example: we have that i = 1 for the sequence '0040'. The subarray [0, 4, 0] is not sorted, so you have to do a linear search to find the next largest/smallest nonzero digit, which would be located in array[2])

The complexity for the worst case will be O(n).

Can you improve running time? I guess you can if you do some parallel programming, but I have no knowledge of that field to help you, unfortunately.

Answer 5

This recursive function tries to avoid any unnecessary loop

 public static void count0(int min, int ptr)
 {
      int me = 0; // joker
      do {
            array[ptr] = me;
            if (ptr > 0) count0(Math.max(me,min), ptr-1);
            else print(array);
            me = me == 0 ? (min > 0 ? min : 1) : me+1;
      } while (me < base);
 }

Called like this (base 8 for length of 17) to carry less arguments:

 static int array[];
 static int base;

      int leng = 17;
      base = 8;
      array = new int [leng];

      count0 (0, array.length-1);

Recursivity has its price, though.

Answer 6

I didn't measure performance, but think my code is better readable. The idea is, to produce every number of base b and length l by Integer-iteration from 0 to the known number in decimal, using the Java-build-in conversion decimal to base b, then removing the zeros in that number (which is of type String) and testing for ascending order.

The output has to be padded with zeros, so therefore the complicated printf in the end.

public static boolean isAscending (String digits) {
    for (int i = 1; i < digits.length (); ++i)
        if (digits.charAt (i-1) > digits.charAt (i)) 
            return false;
    return true;
}

public static void count (int base, int size)
{
    /** 
        Build numbers,i.e. from 000 to 333, for base 4 at length 3
        or 4^3 = 4*4*4 = 64 combinations 
    */      
    double max = Math.pow (base, size);
    for (int i = 0; i < max; ++i)
    {
        String res = Integer.toString (i, base);
        if (isAscending (res.replaceAll ("0", "")))
            System.out.printf ("%0"+size+"d ", Long.parseLong (res)); 
    }
}

Answer 7

Late to the party for this faster answer:

Base               8
Size              20 digits
Current solution: 79 seconds (76~82)
Solution below:   23 seconds (22~24)
Possible numbers: 12245598208

without prints. Principle:

The rule "a digit may be followed by a 0 or a digit >= preceding ones" is also valid for (valid) groups of digits: "a group may be followed by a group of zeroes, or a group which smaller digit is >= any of the preceding ones among the preceding groups". Processing is done at the group level, rather than at the digit level.

Given T total size, and N smaller number of digits in each group (T % N == 0), by calculating all possible groups of N digits they can then be assembled together (T / N groups per solution).

• pre-calculate all possible digits on a smaller size, eg 5 (2668 numbers), in an array (takes less than half a second)
• keep the maximum digit for each of the "parts" in another array
• set in another "atleast" array the indexes of groups based on their smaller digit
• build the large numbers by sticking all possible chunks (eg 4x5), provided that the lower digit of a group has to be >= highest of the preceding groups.

Sample code to precalculate the small chunks (parts)

 static ArrayList<int[]> parts = new ArrayList<int[]>();
 static ArrayList<ArrayList<Integer>> atleast = new ArrayList<ArrayList<Integer>>();
 static ArrayList<Integer> maxi = new ArrayList<Integer>();
 static int stick[];
 static int base;
 static long num = 0;

 public static void makeParts(int min, int ptr)
 {
      int me = 0;
      do {
            array[ptr] = me;
            if (ptr > 0) makeParts(Math.max(me,min), ptr-1);
            else {
                 // add part
                 int[] newa = new int [array.length];
                 int i,mi,ma,last=array.length-1;
                 for (i=0 ; i<array.length ; i++) newa[i] = array[i];
                 parts.add(newa);
                 // maxi
                 for (i=0 ; i<=last && newa[i]==0 ; i++) /* */;
                 maxi.add(ma = i<=last ? newa[i] : 0);
                 // mini
                 for (i=last ; i>=0 && newa[i]==0 ; i--) /* */;
                 mi = i>=0 ? newa[i] : 0;
                 // add to atleast lists
                 int pi = parts.size() - 1;
                 ArrayList<Integer> l;
                 int imi = mi == 0 ? base-1 : mi;
                 for (i=0 ; i<=imi ; i++) {
                      if (i < atleast.size()) l = atleast.get(i);
                      else {
                            l = new ArrayList<Integer>();
                            atleast.add(i, l);
                      }
                      l.add(pi);
                 }
            }
            me = me == 0 ? (min > 0 ? min : 1) : me+1;
      } while (me < base);
 }

Sticking the "parts"

 public static void stickParts(int minv, int ptr)
 {
      // "atleast" gives indexes in "parts" of groups which min digit
      // is at least "minv" (or only zeroes)
      for (int pi: atleast.get(minv)) {
            stick[ptr] = pi;
            if (ptr > 0) {
                 stickParts(Math.max(minv,maxi.get(pi)), ptr-1);
            }
            else {
                 // count solutions
                 // the number is made of "parts" from indexes
                 // stored in "stick"
                 num++;
            }
      }
 }

Calling this in "main"

      base = 8;
      int leng  = 20;
      int pleng =  4;

      array = new int [pleng];

      makeParts(0,array.length-1);

      num = 0;
      stick = new int [leng / pleng];
      stickParts(0, (leng/pleng) - 1);

      out.print(String.format("Got %d numbers\n", num));

If T (total size) is prime, for instance, another specific group has to be calculated, eg for size 17, we could have 3 groups (of 5 digits) + one group of two digits.