Code

Coding, Programming & Algorithms, Tips, Tweaks & Hacks
Search

Sponsored Ads

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.

Vanakkam !