.NET/WebApp/NoSql/Mvvm/and more…

Project Euler problem 24~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?");
  8:             sw.Start();
  9:             var sum1 = test1();
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("using Knuth's algorithm way(ms:{0}): {1}", sw.ElapsedMilliseconds, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("Press any key to exit");
 16:             Console.ReadKey();
 17:         }
 18: 
 19:         /// <summary>
 20:         /// see http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
 21:         /// on section of "Systematic generation of all permutations"
 22:         /// </summary>
 23:         /// <returns></returns>
 24:         static string test1()
 25:         {
 26:             var a = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 27:             var j = 0;
 28:             var l = 0;
 29:             var tmp = 0;
 30:             var len = a.Length;
 31:             var z = 0;
 32:             var counter = 999999; // since the 1st perumation is "a" itself
 33: 
 34:             while (--counter >= 0)
 35:             {
 36:                 //step 1. Find the largest index j such that a[j] < a[j + 1].
 37:                 for (j = len - 2; j >= 0; j--)
 38:                 {
 39:                     if (a[j] < a[j + 1])
 40:                         break;
 41:                 }
 42:                 if (j == -1)
 43:                     break; // no more permutation, since no such index exist
 44: 
 45:                 //step 2. Find the largest index l such that a[j] < a[l]
 46:                 for (l = len - 1; l >= 0; l--)
 47:                 {
 48:                     if (a[j] < a[l])
 49:                         break;
 50:                 }
 51: 
 52:                 //step 3. Swap a[j] with a[l].
 53:                 tmp = a[j];
 54:                 a[j] = a[l];
 55:                 a[l] = tmp;
 56: 
 57:                 //step 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]
 58:                 z = len - 1;
 59:                 for (l = j + 1; l < len; l++)
 60:                 {
 61:                     if (l >= z)
 62:                         break;
 63: 
 64:                     tmp = a[l];
 65:                     a[l] = a[z];
 66:                     a[z] = tmp;
 67:                     z--;
 68:                 }
 69:             }
 70:             return a.Aggregate(string.Empty, (s, n) => s += n);
 71:         }
 72:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s