svagionitis/Makefile

## 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;
}
	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
	#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;
	}