Odometer algorithm.

odometer.c

#include <stdlib.h>
#include <stdio.h>

/**
 * \brief Compute the exponential power for uint64_t
 *
 * \param   base    The base to be expanded.
 * \param   exp     The exponential.
 * \return  the computed power exponential.
 */
uint64_t pow1(uint64_t base, uint64_t exp)
{
    uint64_t t = 1;

    if (exp == 0)
        return 1;
    else if (exp == 1)
        return base;
    else if (exp == 2)
        return base*base;
    else
    {
        for(uint64_t i = 0;i<exp;i++)
            t*=base;
    }

    return t;
}

/**
 * \brief Implements a modified odometer algorithm, it's a permutation of N digits,
 *        which each digit has a maximum value of MAX_VAL. For example, if N = 5
 *        and the MAX_VAL = 3, we get the following permutations
 *
 *        0 0 0 0 0
 *        1 0 0 0 0
 *        2 0 0 0 0
 *        0 1 0 0 0
 *        1 1 0 0 0
 *        2 1 0 0 0
 *        0 2 0 0 0
 *        1 2 0 0 0
 *        2 2 0 0 0
 *        0 0 1 0 0
 *        1 0 1 0 0
 *        2 0 1 0 0
 *        ...
 *        ...
 *        2 2 2 2 2
 *
 *        The total number of permutations is MAX_VAL^N, in the above example,
 *        the total permutations will be 3^5 = 243.
 *
 * \param   sz          It's the N digits to permut.
 * \param   max_num     It's the MAX_VAL of each digit.
 * \return  1 if everything is ok, 0 otherwise.
 */

uint8_t odometer_algo(uint64_t sz, uint64_t max_num)
{
    uint64_t count = 0;
    uint64_t *a = calloc(sz, sizeof(uint64_t));
    if (a == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }

    // Calculate the increase_num_every only once
    uint64_t *increase_num_every = calloc(sz, sizeof(uint64_t));
    if (increase_num_every == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }
    for (uint64_t i = 0;i<sz;i++)
        increase_num_every[i] = pow1(max_num, i);


    uint64_t max_combinations = pow1(max_num,sz);

    while(count < max_combinations)
    {
        fprintf(stdout, "%ju - ", count);
        for (uint64_t i = 0;i<sz;i++)
        {
            if (count)
            {
                if (!(count % increase_num_every[i]))
                {
                    a[i] += 1;
                    a[i] %= max_num;
                }
            }
            fprintf(stdout, "%ju ", a[i]);
        }
        fprintf(stdout, "\n");

        count++;
    }

    if (a)
        free(a);

    if (increase_num_every)
        free(increase_num_every);

    return 1;
}

int main(int argc, char *argv[])
{

    odometer_algo(5, 3);

    return 1;
}