Permutation Generation

Generating permutations of a sequence is a problem that is commonly asked. It's fairly easy to do if you know how many items will be used beforehand, but a generic method to do so would be better.

The snippet will do a lazy generation of the permutations (the next one is only done when it is requested). You can also request a specific permutation (from the lexical order) by calling a method directly, or using indexing.

How to use:
First you need an array of objects that you wish to permutate. Once you have that you call the constructor for the class, passing in the array. Like all generics, you'll have to provide the type of the objects. You are now ready to get your permutations.

The test example will take an array of four strings and:
Display how many different permutations there are.
Display all the permutations of the strings.
Display the fourth lexical permutation using a method call.
Display the sixth lexical permutation using indexing.

using System;
using System.Text;
using Whittle.Math;

namespace Whittle {
    class Program {
        static void Main(string[] args) {
            int counter = 0;
            String[] myItems = { "A", "B", "C", "D" };
            Permutation<String> myPerms = new Permutation<string>(myItems);

            Console.WriteLine("For {0} items there are {1} permutations", myItems.Length, myPerms.NumberOfPermutations);
            Console.WriteLine();
            foreach (String[] perm in myPerms) {
                Console.Write("{0} ", SeqFormat(perm));
                counter = (counter + 1) % 6;
                if (counter == 0) Console.WriteLine();
            }
            Console.WriteLine();
            Console.WriteLine("The fourth lexical permutation is {0}", SeqFormat(myPerms.GetPermutation(4)));
            Console.WriteLine();
            Console.WriteLine("The sixth lexical permutation is {0}", SeqFormat(myPerms[6]));

            Console.ReadLine();
        }

        static String SeqFormat(String[] strings) {
            StringBuilder sb = new StringBuilder();
            sb.Append("[");
            foreach (String s in strings) {
                sb.Append(s);
            }
            sb.Append("]");

            return sb.ToString();
        }
    }
}

How it works:
To understand how the code works you need to understand the factorial number system (also known as the factoradic). This is just like any other number base, but instead of each position (as you move to the left) being the next successive power of the base, it's the next successive factorial.

First (rightmost) position is 0!
Second is 1!
Third is 2!
Fourth is 3! ... etc ...

Let's say we wanted the 500th lexical permutation of the numbers from 1 to 6. Since we have six items, the factoradic will contain six numbers from 5! to 0!. 5! = 120, and since 120 goes into 500 four times (480) the first digit of our number is 4. We subtract the 480 from 500 giving us with 20. 4! is 24, which is greater than 20 so our next digit is 0. 3! is 6, 6 times 3 is 18 so the next digit is 3 with 2 left. 2! is 2 which gives us a 1 with nothing left over so the rest of the digits are 0. Putting this all together gives is the final factoradic of (4,0,3,1,0,0). Something you'll notice is that all factoradics end in 0. If you are generating one and it doesn't, then you've done something wrong.

Now we use the factoradic, digit by digit, as an index into an array of our sequence. But each time we use a number we remove it from the sequence. Continuing our example:

Sequence (1, 2, 3, 4, 5, 6) - Factoradic digit (4) - Indexed number 5 (index is 0 based, just like C#)
Sequence (1, 2, 3, 4, 6) - Factoradic digit (0) - Indexed number 1
Sequence (2, 3, 4, 6) - Factoradic digit (3) - Indexed number 6
Sequence (2, 3, 4) - Factoradic digit (1) - Indexed number 3
Sequence (2, 4) - Factoradic digit (0) - Indexed number 2
Sequence (4) - Factoradic digit (0) - Indexed number 4

So our 500th permutation is (5, 1, 6, 3, 2, 4)

Limitations: Because this requires the generation of factorials the number of items in a list is limited to 12. This can be extended by changing the factorial method to use a numeric type other than int, but then the generation time of the factorial increases. Also note that duplicate entries are treated as unique entries (In a sequence of (1, 1, 2) each of the 1's is treated as a different value).

Acknowledgments: I'd like to acknowledge the article on Factorial Number Systems from Wikipedia and the 2006 MSDN Article "Test Run" by Dr. James McCaffrey which got me interested in this subject in the first place.