DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Roger has posted 34 posts at DZone. View Full User Profile

Odometer-like Brute Force Counter In C

05.04.2011
| 1841 views |
  • submit to reddit
        // 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. 

int odometer(int digits[], int range, int numDigits) {
    int index[range];
    memset(index, 0, sizeof (index));
    int result[range];
    memset(result, 0, sizeof (result));
    int x; //, tempindex;

    /* initialize result to the first digit */
    for (x = 0; x < range; x++) {
        result[x] = digits[index[x]];
    }

    /* go to the right-most digit in result */
    int p = range - 1;

    bool done = false;
    while (!done) {
        for (x = 0; x < range; x++) {
            printf("%d ", result[x]);
        }
        printf("\n");

        if (result[p] < digits[numDigits-1]) {
            result[p] = digits[++index[p]];
        } else {
            /* move left until you find a number < greatest digit */
            while (p >= 0 && result[p] == digits[numDigits-1]) {
                --p;
            }
            if (p < 0) {
                done = true;
            } else {
                result[p] = digits[++index[p]];
                while (p < (range-1)) {
                    p++;
                    result[p] = digits[0];
                    index[p] = 0;
                }
            }
        }
    }

    return EXIT_SUCCESS;
}

    
    Tags:
  • C