All Possible Permutations

All possible permutations of a string - Total number of permutations of a given word taking all n letters is n!.
For example, the word post will give 24 possible permutations inclusive of the original word (post).

1. post
2. pots
3. psot
4. psto
5. ptos
6. ptso
7. opts
8. opst
9. ostp
10. ospt
11. otsp
12. otps
13. spot
14. spto
15. sopt
16. sotp
17. stpo
18. stop
19. tpso
20. tpos
21. tosp
22. tops
23. tsop
24. tspo

This snippet here doesn't exactly output permutations of a string, but its indexes - which should correspond to the array indexes.

C++

// All possible permutations upto n digits

#include<fstream.h>
#include<conio.h>

unsigned long fact(unsigned long);
void swap(int[], int, int);
void display(int[]);
void Add(int[], int);

ofstream fout("out.txt");

void main()
 {
        int j, k, n;
        unsigned long i;

        cout << "How many digits ? "; cin >> n;

        int *key = new int[n + 1];
        key[0] = n; // n contains the total no: of digits

        for (i = 1; i <=key[0]; i++)
         key[i] = i;

        display(key);
        swap(key, key[0], key[0] - 1);
        display(key);

        for (i = 3; i <= fact(key[0]); i+=2)
         {
                for (j = key[0] - 1; j >= 0; j--)
                 {
                        if ((i-1) % fact(j) == 0)
                         {
                                Add(key, key[0] - j);
                                for (k = 1; k <= key[0] - j - 1; k++)
                                 {
                                        if (key[k] == key[key[0] - j])
                                         {
                                                Add(key, key[0] - j);
                                                k = 0;
                                         }
                                 }
                         }
                 }

                display(key);
                swap(key, key[0], key[0] - 1);
                display(key);
         }

        cout << "Total no: of permutations = " << key[0] << "! = " << i - 1;
        fout.close();
 }

unsigned long fact(unsigned long f) { return f == 0 ? 1: f * fact(f - 1); }

void swap(int k[], int a, int b)
 {
        int t = k[a]; 
        k[a] = k[b];
        k[b] = t; 
 }

void display(int k[])
 {
        for(int i = 1; i <= k[0]; i++)
         fout << k[i];

        fout << '\n';
 }

void Add(int k[], int i)
 {
        k[i]++;
        if (k[i] == k[0] + 1)
         k[i] = 1;
 }

Now, its pretty obvious why I had the permutations written to a file instead of console output. 9! is 362,880 but 10! is 10 times 9! which is more than 3.5 million lines of text.

Update : I have ported the C code in Java with some modifications in the way output is handled. This is much safer than that big for loop.

Java

/*
javac Permutations.java
java Permutations post
*/
public class Permutations
{
        private int[] key;
        private String word, pWord;
        private int n, i = 1;

        public Permutations(String word)
        {
                this.word = word;

                n = word.length();
                key = new int[n + 1];

                for (int i = 1; i <= n; i++)
                 key[i] = i;
        }

        public boolean next()
        {
                if (i == 1)
                {
                        build();
                }
                else if (i == fact(n) + 1)
                {
                        return false;
                }
                else if (i % 2 == 0)
                {
                        swap(n, n - 1);
                        build();
                }
                else if (i % 2 == 1)
                {
                        int j, k;

                        for (j = n - 1; j >= 0; j--)
                        {
                                if ((i - 1) % fact(j) == 0)
                                {
                                        add(n - j);
                                        for (k = 1; k <= n - j - 1; k++)
                                        {
                                                if (key[k] == key[n - j])
                                                {
                                                        add(n - j);
                                                        k = 0;
                                                }
                                        }
                                }
                        }

                        build();
                }

                i++;
                return true;
        }

        private long fact(long f) { return f == 0 ? 1: f * fact(f - 1); }

        private void swap(int a, int b)
        {
                int t = key[a];
                key[a] = key[b];
                key[b] = t;
        }

        private void build()
        {
                StringBuilder s = new StringBuilder();

                for(int i = 1; i <= n; i++)
                 s.append(word.charAt(key[i] - 1));

                pWord = s.toString();
        }

        private void add(int i)
        {
                key[i]++;
                if (key[i] == n + 1)
                 key[i] = 1;
        }

        public String nextWord()
        {
                return pWord;
        }

        public static void main(String[] args)
        {
                if (args.length == 0)
                {
                        System.out.println("Got to give an argument");
                        System.exit(0);
                }

                Permutations p = new Permutations(args[0]);
                while (p.next())
                {
                        System.out.println(p.nextWord());
                }
        }
}

JDK 1.6

PS: I wrote this half a decade ago but never documented it. I'll try to update it with an explanation soon.