Permutations of a number with N digits using the Fischer and Krause algorithm.

perm_digits.c

/**
 * @file     perm_digits.c
 * @author   Stavros Vagionitis
 * @date     17 Mar 2015
 * @brief    Calculate the permutations of an N-digit number
 *           without using an array and using the Fischer and Krause algorithm.
 *
 */

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

/**
 * \brief Count the digits of a number
 *
 * \param   num     The number to count the digits
 * \return the number of digits.
 */
uint64_t count_digits(const uint64_t num)
{
    uint64_t counter = 0;
    uint64_t n = num;

    while(n)
    {
        n /= 10;
        counter++;
    }

    return counter;
}

/**
 * \brief Count zeros in the digit
 *
 * \param   num     The number to count zeros
 * \return the number of zeros counted
 */
uint64_t count_zeros(const uint64_t num)
{
    uint64_t counter = 0;
    uint64_t n = num;

    while(n)
    {
        uint64_t d = n % 10;

        if (!d)
            counter++;

        n/=10;
    }

    return counter;
}

/**
 * \brief Remove a specific number of zeros
 *
 * \param   num                 The number to remove zeros
 * \param   zeros_to_remove     The number of zeros to remove
 * \return the number without the specified number of zeros
 */
uint64_t remove_zeros(const uint64_t num, uint64_t zeros_to_remove)
{
    uint64_t n = num;
    uint64_t dec = 1;
    uint64_t out_num = 0;

    while(n)
    {
        uint64_t d = n % 10;

        // If the digit is zero and the
        // remaining number of zeros is positive
        // then continue to the next digit
        // without adding it to the output number
        if (!d && zeros_to_remove>0)
        {
            n/=10;
            zeros_to_remove--;
            continue;
        }

        out_num += (d*dec);

        n/=10;
        dec *= 10;
    }

    return out_num;
}

/**
 * \brief Swap the digits from two positions
 *        It's a naive approach because this implementation iterates
 *        the number twice
 *              *   once to find the digits
 *              *   second to reconstruct the number with the digits
 *                  swapped
 *
 *        There must be a more efficient way to do that.
 *
 *        TODO Find a more efficient way to swap the digits.
 *
 * \param   num         The number to swap the digits
 * \param   out_num     The number with the digits swapped
 * \param   dpos1       The first position to swap
 * \param   dpos2       The second position to swap
 * \return 1 if everything was ok, 0 if not
 */
uint8_t swap_digits(const uint64_t num, uint64_t *out_num, uint64_t dpos1, uint64_t dpos2)
{
    uint64_t cd = count_digits(num);
    uint64_t n = num;
    // Digits to be swapped.
    uint64_t d1 = 0, d2 = 0;

    // If the position of the digits
    // to swap are larger than the total
    // number of digits then return false.
    // Return false if the positions are zeros
    if (dpos1 > cd-1 || dpos2 > cd-1)
        return 0;

    // Get the digits of the specified
    // positions.
    uint64_t pos = cd-1;
    while(n)
    {
        uint64_t d = n % 10;

        if (dpos1 == pos)
            d1 = d;
        if (dpos2 == pos)
            d2 = d;

        n /= 10;
        pos -= 1;
    }

    // Reconstruct the number with the
    // digits swapped.
    *out_num = 0;
    uint64_t dec = 1;
    n = num;
    pos = cd-1;
    while(n)
    {
        uint64_t d = n % 10;

        if (dpos1 == pos)
            d = d2;
        if (dpos2 == pos)
            d = d1;

        *out_num += (d*dec);

        n /= 10;
        pos -= 1;
        dec *= 10;
    }

#if 0
    fprintf(stdout,"%ju -> %ju\n", num, out_num);
#endif

    return 1;
}

/**
 * \brief Get the digit from a specific position
 *
 * \param   num     The number to get the digit
 * \param   pos     The position to retrieve the digit from the number.
 * \return the digit from a specific position.
 */
uint64_t get_digit(const uint64_t num, uint64_t pos)
{
     uint64_t cd = count_digits(num);
     uint64_t n = num;

    // Get the digit of the specified
    // position.
    uint64_t p = cd-1;
    while(n)
    {
        uint64_t d = n % 10;

        if (p == pos)
            return d;

        n /= 10;
        p -= 1;
    }
}

/**
 * \brief Find the next permutation using the Fischer and Krause algorithm.
 *
 * \param   num     [IN/OUT] The number to permute
 * \return 1 if there is another permutation, 0 if not or error.
 */
uint8_t make_next_perm(uint64_t *num)
{
    uint64_t cd = count_digits(*num);
    uint64_t i = cd-1;
    uint64_t j = i;
    uint64_t k = j;

    while (i && get_digit(*num, i - 1) >= get_digit(*num, i))
        --i;

    if (!i)
        return 0;

    while (get_digit(*num, j) <= get_digit(*num, i - 1))
        --j;

    if (swap_digits(*num, num, i - 1, j) == 0)
        return 0;

    while (i < k)
    {
        if (swap_digits(*num, num, i, k) == 0)
            return 0;

        i++;k--;
    }

    return 1;
}

/**
 * \brief Find all lexicographic permutations
 *
 * \param   num     The number to permute
 */
void lexico_perm(const uint64_t num)
{
    uint64_t n = num;
    uint64_t c = 0;

    while(1)
    {
        do
        {
            fprintf(stdout, "%ju: %ju\n", c, n);
            c++;
        }while(make_next_perm(&n));

        if (count_zeros(n))
        {
            n = num;
            n = remove_zeros(n, 1);
        }
        else
            break;
    }

    fprintf(stdout, "Total %ju permutations\n", c);
}

/**
 * \brief Find all permutations
 *        The algorithm used here can be found in
 *        http://www.quickperm.org/pseudo2.php
 *
 *
 * \param   num     The number to permute
 */
uint8_t perm(const uint64_t num)
{
    uint64_t n = num;
    uint64_t cd = count_digits(num);
    uint64_t *p = calloc(cd, sizeof(uint64_t));
    if (p == NULL)
    {
        fprintf(stderr, "%s:%d Mem Alloc failed\n", __func__, __LINE__);
        return 0;
    }

    for (uint64_t i = 0;i<cd;i++)
        p[i] = i;


    uint64_t i = 1;
    uint64_t j = 0;
    uint64_t c = 0;

    while(i<cd)
    {
        if (p[i]>0)
        {
            p[i]--;
            j = 0;

            if (i%2 != 0)
                j = p[i];

            swap_digits(n, &n, j, i);
            fprintf(stdout, "%ju: %ju\n", c, n);
            c++;
            i = 1;
        }
        else
        {
            p[i] = i;
            i++;
        }
    }

    fprintf(stdout, "Permutations counted for digits %ju is %ju.\n", cd, c);

    if (p)
        free(p);

    return 1;
}

/**
 * \brief Usage of this program.
 *
 * \param   argv0   The first argument string which is the current executable.
 * \return  -1.
 */
int usage(char *argv0)
{
    fprintf(stdout, "%s <Number to permute>\n", argv0);
    return -1;
}

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

    // Problem with 0
    // TODO Fix problem with 0.
    uint64_t num = strtoull(argv[1], NULL, 10);

    lexico_perm(num);

    perm(num);

    return 1;
}