﻿using System; using System.Collections.Generic; using System.Diagnostics; namespace euler { class Problem24 { public static void Main(string[] args) { new Problem24().BruteForce(); new Problem24().Factorial(); } #region BruteForce int[] perm = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; public void BruteForce() { Stopwatch clock = Stopwatch.StartNew(); int count = 1; int numPerm = 1000000; while (count < numPerm) { int N = perm.Length; int i = N-1; while (perm[i - 1] >= perm[i]) { i = i - 1; } int j = N; while (perm[j - 1] <= perm[i - 1]) { j = j - 1; } // swap values at position i-1 and j-1 swap(i - 1, j - 1); i++; j = N; while (i < j) { swap(i - 1, j - 1); i++; j--; } count++; } string permNum = ""; for (int k = 0; k < perm.Length; k++) { permNum = permNum + perm[k]; } clock.Stop(); Console.WriteLine("The millionth lexicographic permutation is: {0}", permNum); Console.WriteLine("Solution took {0} ms", clock.ElapsedMilliseconds); } private void swap(int i, int j) { int k = perm[i]; perm[i] = perm[j]; perm[j] = k; } #endregion bruteforce #region Factorial public void Factorial() { Stopwatch clock = Stopwatch.StartNew(); int N = perm.Length; string permNum = ""; int remain = 1000000-1; List numbers = new List(); for (int i = 0; i < N; i++) { numbers.Add(i); } for (int i = 1; i < N; i++) { int j = remain / Factor(N - i); remain = remain % Factor(N - i); permNum = permNum + numbers[j]; numbers.RemoveAt(j); if (remain == 0) { break; } } for (int i = 0; i < numbers.Count; i++) { permNum = permNum + numbers[i]; } clock.Stop(); Console.WriteLine("The millionth lexicographic permutation is: {0}", permNum); Console.WriteLine("Solution took {0} ms", clock.ElapsedMilliseconds); } private int Factor(int i) { if (i < 0) { return 0; } int p = 1; for (int j = 1; j <= i; j++) { p *= j; } return p; } #endregion Factorial } }