Print all numbers whose nonzero digits are in ascending order.

Question

I am trying to write a program that takes the number of digits and the base as arguments, and counts up numbers that have nonzero digits in ascending order. For example, in the 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 should be printed:

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 did it successfully, but my algorithm seems unnecessarily complicated and time-consuming (time is very important for my application). Is there a way to make it faster or simplify if 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

Late side for this quick reply:

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

no stamp. Principle:

The rule "a digit may be followed by 0 or a digit> = previous" is also valid for (valid) groups of digits: "a group may be followed by a group of zeros or a group that is less than digit> = any of the previous from previous groups". Processing is done at the group level, not at the level of numbers.

Given a T total size and N fewer digits in each group (T% N == 0), calculating all possible groups of N digits, they can be assembled together (T / N groups for each solution).

• pre-compute all possible smaller digits, for example 5 (2668 numbers), in an array (takes less than half a second)
• save the maximum digit for each of the "parts" in another array
• set group indices in another "atleast" array based on their smaller digit
• build large numbers by inserting all possible pieces (e.g. 4x5), provided that the bottom digit of the group must be> = the highest of the previous groups.

Sample code for preliminary calculation of small pieces (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); } 

Bonding "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++; } } } 

The challenge of this in the "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 simple, for example, another specific group should be calculated, for example, for size 17, we could have 3 groups (of 5 digits) + one group of two digits.

Answer 2

I would choose 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 puts the numbers one by one in an array and abides by the restriction that nonzero digits should not be reduced.

Answer 3

Ok, this is a little trickster, but here is the solution expressed in pseudo-code:

 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, in fact, a question about the decimal representation of numbers, and not in a sense the numbers themselves.

The time complexity is O (n), of course - at least calculating str(i) in one step, and this is somewhere a little cheating.

Just for fun, here is 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 nonzero digits, i.e. ['1','2','3','4','5','6','7','8','9'] . List all the lines in this list of length ceil(log10(max)) (quiz question, why is this limit?).

Print these lines in order, stopping when max exceeded.

Answer 4

If you don't mind keeping the numbers in memory, you can encode the following algorithm:

• Start with numbers 0.1 ... base-1
• For each digit d added, first add a zero, and then all previous numbers starting with digits d or higher (indexing by the starting digit and the number of digits, you can access them directly).

Or, like some kind of phrases, dp style: let dp[i][j] represent a sequence of numbers with i digits and the leftmost 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 ++ from Haskell, where it often means 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 5

Pretty interesting program you wrote.

I tried to increase the performance of nested search, but so far I have not found a way to make the worst-case scenario of finding the next non-zero digit less than O (n).

In the worst case, the submatrix A [i..array.length-1] is not sorted, but array [i] = 0, so to find the next nonzero digit, you must do a linear search.

In addition, if there is no next non-zero digit, you need to search the entire array to “find it”.

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

The worst case difficulty will be O (n).

Can you improve your work time? I think you can, if you do parallel programming, but I do not know this field to help you, unfortunately.

Answer 6

I did not evaluate performance, but I think my code is better read. The idea is to produce each base number b and length l using an Integer iteration from 0 to a known number in decimal format, using the Java-build-in decimal conversion to base b, and then removing zeros in that amount (which is of type String) and testing for increasing.

The output must be padded with zeros, so complex printf at 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,ie 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

This recursive function tries to avoid an 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 as (base 8 for length 17) to carry smaller arguments:

  static int array[]; static int base; int leng = 17; base = 8; array = new int [leng]; count0 (0, array.length-1); 

Recursiveness comes at a price.