The odometer algorithm for an alphabet.

Makefile

all: odometer_alphabet

odometer_alphabet: odometer_alphabet.c
	gcc -o odometer_alphabet -O2 -Wall -W -ansi -pedantic -std=gnu99 odometer_alphabet.c

clean:
	rm -rf odometer_alphabet

odometer_alphabet.c

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

/**
 * \brief Compute the string length
 *        See [libowfat](http://www.fefe.de/libowfat/) for more info.
 *
 * \param   in      The string to compute length
 * \return  the length of string
 */
uint64_t str_len(const char* in)
{
    register const char* t=in;

    for (;;)
    {
        if (!*t) break; ++t;
        if (!*t) break; ++t;
        if (!*t) break; ++t;
        if (!*t) break; ++t;
    }

    return (uint64_t)(t-in);
}

/**
 * \brief Compare two strings and check if they are equal.
 *        When the strings are different, str_diff does not read bytes past the
 *        first difference. See [libowfat](http://www.fefe.de/libowfat/) for more info.
 *
 * \param   a      The first string.
 * \param   b      The second string.
 * \return  negative, 0, or positive, depending on whether the
 *          string a[0], a[1], ..., a[n]=='\0' is lexicographically smaller than,
 *          equal to, or greater than the string b[0], b[1], ..., b[m-1]=='\0'.
 */
int64_t str_diff(const char* a, const char* b)
{
    register const unsigned char* s=(const unsigned char*) a;
    register const unsigned char* t=(const unsigned char*) b;
    register int64_t j;
    j=0;

    for (;;)
    {
        if ((j = (*s - *t))) break; if (!*t) break; ++s; ++t;
        if ((j = (*s - *t))) break; if (!*t) break; ++s; ++t;
        if ((j = (*s - *t))) break; if (!*t) break; ++s; ++t;
        if ((j = (*s - *t))) break; if (!*t) break; ++s; ++t;
    }

    return j;
}

/**
 * \brief find character in ASCIIZ string
 *        See [libowfat](http://www.fefe.de/libowfat/) for more info.
 *
 * \param   in      The string to search for.
 * \param   needle  The character to search in the string
 * \return  the index of the first occurrance of needle or \0 in string
 */
int64_t str_chr(const char *in, char needle)
{
    register const char* t=in;
    register const char c=needle;

    for (;;)
    {
        if (!*t || *t==c) break; ++t;
        if (!*t || *t==c) break; ++t;
        if (!*t || *t==c) break; ++t;
        if (!*t || *t==c) break; ++t;
    }

    return (int64_t)(t-in);
}


/**
 * \brief Get the next permutation of a given string and alphabet.
 *        For example, if the alphabet is "abc" and if the string is
 *        - "aaab", the next permutation will be "aaac"
 *        - "aaac", the next permutation will be "aaba"
 *        - "cccb", the next permutation will be "cccc"
 *
 * \param   buff            The string to change to the next permutation.
 * \param   buff_sz         The size of the string.
 * \param   alphabet        The alphabet to be used to calculate the next permutation.
 * \param   alpahabet_sz    The size of the alphabet.
 * \return  1 if everything is ok, 0 otherwise.
 */
uint8_t get_next(char* buff, const uint64_t buff_sz, const char* alphabet, const uint64_t alphabet_sz)
{
    if (buff == NULL)
    {
        fprintf(stderr, "%s:%d buff is null\n", __func__, __LINE__);
        return 0;
    }

    if (alphabet == NULL)
    {
        fprintf(stderr, "%s:%d alphabet is null\n", __func__, __LINE__);
        return 0;
    }

    for (int64_t i = buff_sz - 1;i != -1;i--)
    {
        // Get the position of the character in the
        // alphabet string.
        uint64_t pos = str_chr(alphabet, buff[i]);


        // If the character, is the last character
        // of the alphabet, change to the first character
        // of the alphabet and continue to the next character
        // on buffer.
        if (buff[i] == alphabet[alphabet_sz - 1])
        {
            buff[i] = alphabet[(pos+1) % alphabet_sz];
            continue;
        }
        else
        {
            buff[i] = alphabet[(pos+1) % alphabet_sz];
            break;
        }
    }

    return 1;
}

/**
 * \brief Implements a modified odometer algorithm, it's a permutation of N members of an alphabet,
 *        which each member of the alphabet can take MAX_VAL values. For example, if N = 5
 *        and the alphabet "abc" (MAX_VAL = 3), we get the following permutations
 *
 *        a a a a a
 *        b a a a a
 *        c a a a a
 *        a b a a a
 *        b b a a a
 *        c b a a a
 *        a c a a a
 *        b c a a a
 *        c c a a a
 *        a a b a a
 *        b a b a a
 *        c a b a a
 *        ...
 *        ...
 *        c c c c c
 *
 *        The total number of permutations is MAX_VAL^N, in the above example,
 *        the total permutations will be 3^5 = 243.
 *
 * \param   buff_sz     It's the N members to permut (actually it's the buffer size).
 * \param   alphabet    The alphabet that will be used.
 * \param   alphabet_sz It's the MAX_VAL of each member (actually it's the size of the alphabet).
 * \return  1 if everything is ok, 0 otherwise.
 */

uint8_t odometer_algo2(const uint64_t buff_sz, const char* alphabet, const uint64_t alphabet_sz)
{
    uint64_t count = 0;

    // The buffer that holds the changes
    char* a = calloc(buff_sz, sizeof(char));
    if (a == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }
    // Initialize with the first member of alphabet
    for (uint64_t i = 0;i < buff_sz;i++)
        a[i] = alphabet[0];


    // The end result of the buffer
    char* e = calloc(buff_sz, sizeof(char));
    if (e == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }
    // Initialize with the last member of alphabet
    for (uint64_t i = 0;i < buff_sz;i++)
        e[i] = alphabet[alphabet_sz - 1];


    while(str_diff(a, e))
    {
        fprintf(stdout, "%ju: ", count);

        get_next(a, buff_sz, alphabet, alphabet_sz);

        fprintf(stdout, "%s\n", a);

        count++;
    }

    if (a)
        free(a);

    if (e)
        free(e);

    return 1;
}

/**
 * \brief Implements a modified odometer algorithm, it's a permutation of N members of an alphabet,
 *        which each member of the alphabet can take MAX_VAL values. For example, if N = 5
 *        and the alphabet "abc" (MAX_VAL = 3), we get the following permutations
 *
 *        a a a a a
 *        b a a a a
 *        c a a a a
 *        a b a a a
 *        b b a a a
 *        c b a a a
 *        a c a a a
 *        b c a a a
 *        c c a a a
 *        a a b a a
 *        b a b a a
 *        c a b a a
 *        ...
 *        ...
 *        c c c c c
 *
 *        The total number of permutations is MAX_VAL^N, in the above example,
 *        the total permutations will be 3^5 = 243.
 *
 * \param   buff_sz     It's the N members to permut (actually it's the buffer size).
 * \param   alphabet    The alphabet that will be used.
 * \param   alphabet_sz It's the MAX_VAL of each member (actually it's the size of the alphabet).
 * \return  1 if everything is ok, 0 otherwise.
 */

uint8_t odometer_algo1(const uint64_t buff_sz, const char* alphabet, const uint64_t alphabet_sz)
{
    uint64_t count = 0;

    // The buffer that holds the changes
    char* a = calloc(buff_sz, sizeof(char));
    if (a == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }
    // Initialize with the first member of alphabet
    for (uint64_t i = 0;i < buff_sz;i++)
        a[i] = alphabet[0];


    // The end result of the buffer
    char* e = calloc(buff_sz, sizeof(char));
    if (e == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }
    // Initialize with the last member of alphabet
    for (uint64_t i = 0;i < buff_sz;i++)
        e[i] = alphabet[alphabet_sz - 1];


    // Keep the position of alphabet in each position of buffer
    uint64_t* pos_alphabet = calloc(buff_sz, sizeof(uint64_t));
    if (pos_alphabet == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }


    while(str_diff(a, e))
    {
        fprintf(stdout, "%ju: ", count);

        // The first position of buffer is changing in every iteration;
        pos_alphabet[0] = count % alphabet_sz;

        for (uint64_t i = 0;i < buff_sz;i++)
        {
            a[i] = alphabet[pos_alphabet[i]];

            // If the previous positions of the buffer have as a value
            // the last member of alphabet, then it will change in the next iteration.
            uint64_t j = i;
            while(j != 0)
            {
                // If the previous position of buffer is the last
                // member of alphabet, then continue to the previous
                if (a[--j] == alphabet[alphabet_sz - 1])
                {
                    // If it's the first position, then calculate the next position
                    if (j == 0)
                        pos_alphabet[i] = (pos_alphabet[i] + 1) % alphabet_sz;

                    continue;
                }
                else
                    break;
            }
        }

        fprintf(stdout, "%s\n", a);

        count++;
    }

    if (a)
        free(a);

    if (e)
        free(e);

    if (pos_alphabet)
        free(pos_alphabet);

    return 1;
}

void usage(char *argv0)
{
    fprintf(stderr, "Usage: %s <size of the string to permute>\n", argv0);
}

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        usage(argv[0]);
        return -1;
    }

    // TODO Check if it's number
    uint64_t strlen = atoi(argv[1]);

#if 0
    // http://en.wikipedia.org/wiki/ASCII#cite_note-48
    const char* printable = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
#endif
    const char* alphanumeric = " 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

#if 0
    odometer_algo1(strlen, alphanumeric, str_len(alphanumeric));
#endif
    odometer_algo2(strlen, alphanumeric, str_len(alphanumeric));

    return 0;
}