Advanced Search

Odometer-like Brute-force Counter in C

/ Published in: C
Save to your folder(s)
Given a sorted set of digits, print all of them in counting order.
digits[] - the set of digits allowed. They are assumed to be in the set {0-9}, but it will work with larger numbers as well.
range - the length of the resulting number (i.e., how many digits to print)
numDigits - the size of the set of digits represented by digits[]

There are probably slicker ways to do this: see http://stackoverflow.com/questions/228796/algorithm-odometer-brute-force
but this one is fast.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. int odometer(int digits[], int range, int numDigits) {
  2.     int index[range];
  3.     memset(index, 0, sizeof (index));
  4.     int result[range];
  5.     memset(result, 0, sizeof (result));
  6.     int x; //, tempindex;
  7.  
  8.     /* initialize result to the first digit */
  9.     for (x = 0; x < range; x++) {
  10.         result[x] = digits[index[x]];
  11.     }
  12.  
  13.     /* go to the right-most digit in result */
  14.     int p = range - 1;
  15.  
  16.     bool done = false;
  17.     while (!done) {
  18.         for (x = 0; x < range; x++) {
  19.             printf("%d ", result[x]);
  20.         }
  21.         printf("\n");
  22.  
  23.         if (result[p] < digits[numDigits-1]) {
  24.             result[p] = digits[++index[p]];
  25.         } else {
  26.             /* move left until you find a number < greatest digit */
  27.             while (p >= 0 && result[p] == digits[numDigits-1]) {
  28.                 --p;
  29.             }
  30.             if (p < 0) {
  31.                 done = true;
  32.             } else {
  33.                 result[p] = digits[++index[p]];
  34.                 while (p < (range-1)) {
  35.                     p++;
  36.                     result[p] = digits[0];
  37.                     index[p] = 0;
  38.                 }
  39.             }
  40.         }
  41.     }
  42.  
  43.     return 0;
  44. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.