Posted By

rtperson on 06/01/11


Tagged


Versions (?)

Odometer-like Brute-force Counter in C


 / Published in: C
 

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.

  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  

You need to login to post a comment.