Print all the permutations of the characters in a word

A interesting computer programming problem is to print the all permutations of a the characters in a word.

How can we do that? Below is a simple approach:

Suppose your word has 'n' chars,
then first letter of your word can have n options,
second n -1 options
third n -2 options
and so on....
last will have just one option.
Trick is to add the options successively to the prefix, and sending
the suffix (i.e.) the options for remaining positions to function
and call the function for printing permutations recursively.


Below is the code for printing permutations of a word. Here I am
not taking into account the case of repeated letters. Which results
in printing duplicates. More thoughts for avoiding printing duplicates
efficiently:). I don't want to use a set to store the words and printing them
at the end. I want an algorithmic way out to solve the issue. Also, in this example the maximum word size is taken as 26, but that can be easily changed; just replace 26 with a bigger number:)

// Below is the code for printing permutations of an word. Here I am
// not taking into account the case of repeated letters. Which results
// in printing duplicates. More thoughts for avoiding printing duplicates
// efficiently. I don't want to use a store the words and printing them
// at them at the end. I want an algorithmic way out to solve the issue
//
// How does it work ?
// Suppose your whord has 'n' chars,
// then first letter of your word can have n options,
// second n -1 options
// third n -2 options
// and so on....
// last will have just one option.
// Trick is to add the options successively to the prefix, and sending
// the suffix (i.e.) the options for remaining positions to function
// and call the function print_permutations_word repeatedly
//

#include <stdio.h>
#include <string.h>

int print_permutations_word(const char *prefix, const char *suffix, int suffixlen)
{
    char myprefix[26] = "";
    char mysuffix[26] = "";
    int i = 0, j = 0, k = 0;
    if (suffixlen == 0) {
        printf("word %s\n", prefix);
        return 0;
    }

    while (i < suffixlen) {
        memset(myprefix, 0, 26);
        memset(mysuffix, 0, 26);
        snprintf(myprefix,26,"%s%c", prefix,suffix[i]);
        j = 0;
        k = 0;
        while (j < suffixlen) {
           if (i != j){
                mysuffix[k++] = suffix[j];
           }
           j++;
        }
        i++;
        print_permutations_word(myprefix, mysuffix, suffixlen - 1);
    }
    return 0;

}

#if 0
//example run
int main()
{
print_permutations_word("", "abcde", 5);
return 0;
}
#endif

Next approach describes how we can print all permutations of the characters using iterative method based on the principle of getting the next permutation. The advantage of this approach is that we don't print duplicates and efficient for longer strings. We start with "smallest" word and successively print the next bigger word stopping at the "biggest" word. Heart of this approach is in getting the next permutation based on the current permutation.

# Given a word(current permutation), how do we find the next permutation?
# ------------------------------
# Start from last char and successively compare a char to the character in its
# left. If the left character is smaller than the current character (say the
# position of the left character is exchange position), exchange the left
# charecter with a charecter to its right which is bigger than it and
# nearest to it. When the exchange happens, sort the character array to the
# right of the exchange position.
# Repeat the above process until the iteration when no exchange of characters
# happens (i.e. it reaches the "biggest" word)
Below example describes the approach:

Current permutation “aerqpdcb”, it is represented in the array below:

a

e

r

q

p

d

c

b

Start with rightmost char (b) and proced left to find the first character which is smaller than its right character.

So, we reached 'e' (exchange position is 1).

On the right side of e, we find p is the character which is bigger than e and nearerst to it.

Exchange, p and e and the array now becomes:

a

p

r

q

e

d

c

b

Now, sort the array to the right of exchange position and the array becomes:

a

p

b

c

d

e

q

r

So, next permutation after “aerqpdcb” is “apbcdeqr”


Below is the Python program (also available at github )  that
implements the approach:

# Below function demonstrates how we can print the permutations of the letters
# in a word

###############################################################################
# HOW it works?
# it starts with the "smallest" possible word and successively prints the next
# bigger word. For example, the smallest possible word from the chars in 
# word 'axprq' is 'apqrx' and then the next bigger word is 'apqxr' and so on.
# It stops after printing the "biggest" word which is 'xrqpa'.
#
# The advantage of this algorithm is that we don't print any duplicate words.
#
#
# Given a word(current permutation), how do we find the next permutation?
# ------------------------------ 
# Start from last char and successively compare a char to the character in its
# left. If the left character is smaller than the current character (say the 
# position of the left character is exchange position), exchange the left 
# charecter with a charecter to its right which is bigger than it and
# nearest to it. When the exchange happens, sort the character array to the 
# right of the exchange position.
# Repeat the above process until the iteration when no exchange of characters
# happens (i.e. it reaches the "biggest" word)

def print_permute(word):
    a = sorted(word)
    l = len(word)
    exchanged = True
    while exchanged:
        print ''.join(a)
        i = l - 1
        exchanged = False
        while i != 0:
            if a[i] <= a[i - 1]:
                i -= 1
            else:
                exchanged = True
                j = i + 1
                while j < l:
                    if a[i - 1] < a[j]:
                        j += 1 
                    else:
                        break
                j -= 1
                a[i-1], a[j] = a[j], a[i-1]
                a[i:] = sorted(a[i:])
                break

#Example Run
print ('Printing permutations of xyz')
print_permute('xyz')
print('.............................')
print('.............................')
print ('Printing permutations of abcdd')
print_permute('abcdd')
print('.............................')
print('.............................')
print ('Printing permutations of axprq')
print_permute('axprq')