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

- /*A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the
- digits 1, 2, 3 and 4.
- * If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
- 012 021 102 120 201 210
- What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
- */
- //.01 seconds
- static void Main(string[] args)
- {
- Stopwatch sw = new Stopwatch();
- sw.Start();
- int[] numbers = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
- char[] letters = new char[] {'a','b','c','d','e','f','g','h','i','j'};
- Console.WriteLine(findPermutationAtElement<int>(numbers, 999999));
- Console.WriteLine(findPermutationAtElement<char>(letters, 999999));
- sw.Stop();
- Console.WriteLine(sw.Elapsed);
- Console.ReadLine();
- }
- private static string findPermutationAtElement<T>(T[] numbers, int p)
- {
- string answer = "";
- ulong totalPerms;
- int position;
- ulong section;
- T[] temp;
- int length = numbers.Length;
- //make sure array is ordered
- numbers = numbers.OrderBy(n => n).ToArray();
- for (int i = 0; i < length; i++)
- {
- //find number of permutations left
- totalPerms = factorial(numbers.Length);
- //find what section number will fall into
- section = totalPerms / (ulong)numbers.Length;
- //find whole number index
- position = p / (int)section;
- //change p to reflect sub array position
- p = p % (int)section;
- //put value at the end
- answer = answer.Insert(answer.Length, numbers.ElementAt(position).ToString());
- //remove element from array
- temp = new T[numbers.Length - 1];
- for (int j = 0; j < numbers.Length; j++)
- {
- if (j == position)
- {
- }
- else if (j > position)
- {
- temp[j - 1] = numbers[j];
- }
- else
- {
- temp[j] = numbers[j];
- }
- }
- numbers = temp;
- }
- return answer;
- }
- private static ulong factorial(int p)
- {
- if (p == 0)
- {
- return 1;
- }
- return (ulong)p * factorial(p - 1);
- }

## 1 comment:

Hello sir, can you please explain this algorithm?

Post a Comment