Permutation Generation

Momerath 3 Tallied Votes 1K Views Share

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.

kvprajapati commented: Nice! +12
jonsca commented: Nicely done, very clear explanation to go with it. +6
using System;
using System.Collections;
using System.Collections.Generic;

namespace Whittle.Math {
    /// <summary>
    /// Class to generate all the permutations of an array of objects. This code
    /// is released under the GPL v3 license with the aditional restriction that
    /// any use in a public (commercial or non-commercial) product requires 
    /// notification of the author.
    /// </summary>
    /// <typeparam name="T">The type of objects that will be permutated</typeparam>
    public class Permutation<T> : IEnumerable, IEnumerator {
        private T[] items;
        private int count;
        int current = -1;

        /// <summary>
        /// Constructor for the permutation class
        /// </summary>
        /// <param name="theList">Array of objects that will be permutated</param>
        public Permutation(T[] theList) {
            if (SmallFactorial.MaxFactorial >= theList.Length) {
                this.items = theList;
                this.count = SmallFactorial.Factorial(this.items.Length);
            } else {
                throw new ArgumentOutOfRangeException("Too many items in the list, "
                                + "maximum number of items is " + SmallFactorial.MaxFactorial);
            }
        }

        /// <summary>
        /// Returns the number of permutations that exist for this set of objects
        /// </summary>
        public int NumberOfPermutations {
            get {
                return count;
            }
        }

        /// <summary>
        /// Gets the specific lexical permutation. The first permutation is 0 and ranges to NumberOfPermutations - 1
        /// </summary>
        /// <param name="n">lexical permutation to return</param>
        /// <returns>Array containing the nth lexical permutation</returns>
        public T[] GetPermutation(int n) {
            if (n < 0 || n >= count) {
                throw new IndexOutOfRangeException();
            }

            List<T> result = new List<T>();
            int[] factoradic = new int[items.Length];

            // Find the factoradic
            for (int i = 1; i <= items.Length; i++) {
                factoradic[items.Length - i] = n % i;
                n /= i;
            }

            // Convert the factoradic to the permutation
            List<T> tempList = new List<T>(items);

            for (int i = 0; i < items.Length; i++) {
                result.Add(tempList[factoradic[i]]);
                tempList.RemoveAt(factoradic[i]);
            }

            return result.ToArray();
        }

        /// <summary>
        /// Same as GetPermutation. Allows you to index rather than call a method.
        /// </summary>
        /// <param name="n">lexical permutation to return</param>
        /// <returns>Array containing the nth lexical permutation</returns>
        public T[] this[int n] {
            get {
                return GetPermutation(n);
            }
        }

        /// <summary>
        /// Enumerator for generating permutations in lexical order
        /// </summary>
        /// <returns>Enumerator</returns>
        IEnumerator IEnumerable.GetEnumerator() {
            return this;
        }

        /// <summary>
        /// Curent permutation based on the Enumerator
        /// </summary>
        object IEnumerator.Current {
            get {
                return GetPermutation(current);
            }
        }

        /// <summary>
        /// Moves to the next item.
        /// </summary>
        /// <returns>true if there is another item in the Enumeration, false otherwise</returns>
        bool IEnumerator.MoveNext() {
            current++;
            return (current < count);
        }

        /// <summary>
        /// Resets the Enumerator to the beginning of the Enumeration
        /// </summary>
        void IEnumerator.Reset() {
            current = -1;
        }
    }
}

namespace Whittle.Math {
    static class SmallFactorial {
        static public int Factorial(int n) {
            int result = 1;
            for (int i = 2; i <= n; i++) {
                checked {
                    result *= i;
                }
            }
            return result;
        }

        static public int MaxFactorial {
            get {
                return 12;
            }
        }
    }
}
Momerath 1,327 Nearly a Senior Poster Featured Poster

Just adding a link to Combination Generation in case you ended up here but wanted to be there.

commented: rep you now! +14
ddanbe 2,724 Professional Procrastinator Featured Poster

Great idea! Cannot give you rep because I can do that only once in 24 hours to the same person I think. So the rep turned into a 1.
I have posted some time ago 3 snippets that together form a Console calculator( an expression evaluator really) could be that my scanner looks so scary, that less people loked at the rest or else they could not find it in some way.

Momerath 1,327 Nearly a Senior Poster Featured Poster

I'll try to keep my snippet/tutorial posting down to one every other day then :)

I've looked at the code (snippets are hard to find on this forum, actually, they scroll off the main page and 'time out' on the snippet tab too fast. I took a look at your first posting and it looks good :)

Just a question, have you ever looked at lex/yacc?

ddanbe 2,724 Professional Procrastinator Featured Poster

Yes I did, I even have the Dragon Book!
This calculator is (after many previous trials, which even date from the previous century and in other languages) the culmination of my "efforts" in this field.
Never aimed at building my own compiler, I can tell you that.
I was just curious how a heap of sand and copper and plastic could work out the result of an expression with operator precedance etc.
Lex and yacc take away the burden of figuring that out, but the burden was just what I liked here.
So I did it by myself(well I had some books and info of course). Man, it was FUN!
I you're interested here are the 3 snips:
http://www.daniweb.com/code/snippet217185.html
http://www.daniweb.com/code/snippet217186.html
http://www.daniweb.com/code/snippet217187.html

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.