About Me

My photo
Northglenn, Colorado, United States
I'm primarily a BI Developer on the Microsoft stack. I do sometimes touch upon other Microsoft stacks ( web development, application development, and sql server development).

Thursday, January 08, 2009

Permutations. The nth permutation from an ordered set of permutations.

So, I was doing Euler 24 from Project Euler. I thought of an interesting way of find the nth permutation from a set. Here is my solution:

       
Code Snippet
  1. /*A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the
  2.         digits 1, 2, 3 and 4.
  3.         * If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
  4.         012   021   102   120   201   210
  5.         What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
  6.         */
  7.         //.01 seconds
  8.         static void Main(string[] args)
  9.         {
  10.             Stopwatch sw = new Stopwatch();
  11.             sw.Start();
  12.             int[] numbers = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  13.             char[] letters = new char[] {'a','b','c','d','e','f','g','h','i','j'};
  14.             Console.WriteLine(findPermutationAtElement<int>(numbers, 999999));
  15.             Console.WriteLine(findPermutationAtElement<char>(letters, 999999));
  16.             sw.Stop();
  17.             Console.WriteLine(sw.Elapsed);
  18.             Console.ReadLine();
  19.         }
  20.         private static string findPermutationAtElement<T>(T[] numbers, int p)
  21.         {
  22.             string answer = "";
  23.             ulong totalPerms;
  24.             int position;
  25.             ulong section;
  26.             T[] temp;
  27.             int length = numbers.Length;
  28.             //make sure array is ordered
  29.             numbers = numbers.OrderBy(n => n).ToArray();
  30.             for (int i = 0; i < length; i++)
  31.             {
  32.                 //find number of permutations left
  33.                 totalPerms = factorial(numbers.Length);
  34.                 //find what section number will fall into
  35.                 section = totalPerms / (ulong)numbers.Length;
  36.                 //find whole number index
  37.                 position = p / (int)section;
  38.                 //change p to reflect sub array position
  39.                 p = p % (int)section;
  40.                 //put value at the end
  41.                 answer = answer.Insert(answer.Length, numbers.ElementAt(position).ToString());
  42.                 //remove element from array
  43.                 temp = new T[numbers.Length - 1];
  44.                 for (int j = 0; j < numbers.Length; j++)
  45.                 {
  46.                     if (j == position)
  47.                     {
  48.                     }
  49.                     else if (j > position)
  50.                     {
  51.                         temp[j - 1] = numbers[j];
  52.                     }
  53.                     else
  54.                     {
  55.                         temp[j] = numbers[j];
  56.                     }
  57.                 }
  58.                 numbers = temp;
  59.             }
  60.             return answer;
  61.         }
  62.         private static ulong factorial(int p)
  63.         {
  64.             if (p == 0)
  65.             {
  66.                 return 1;
  67.             }
  68.             return (ulong)p * factorial(p - 1);
  69.         }

1 comment:

Tips said...

Hello sir, can you please explain this algorithm?