Advertisement
Guest User

Untitled

a guest
Dec 16th, 2013
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 4.08 KB | None | 0 0
  1. /*
  2.  *  Write a program that reads a number N and generates and prints
  3.  *  all the permutations of the numbers [1 … N].
  4.  *  Example: n = 3 -> {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}
  5.  */
  6.  
  7. namespace Permutations
  8. {
  9.     using System;
  10.     using System.Collections.Generic;
  11.  
  12.     class Permutations
  13.     {
  14.         static void Main()
  15.         {
  16.             //input
  17.             Console.Write("Enter the number of permutations: ");
  18.             int numberOfPermutations = int.Parse(Console.ReadLine());
  19.  
  20.             //calculations
  21.             //based on the Johnson-Trotter algorithm. More here:
  22.             //http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
  23.  
  24.             int mobileNumber = numberOfPermutations;
  25.             char[] directions = new char[numberOfPermutations];
  26.             int[] numbers = new int[numberOfPermutations];
  27.             for (int index = 0; index < numberOfPermutations; index++)
  28.             {
  29.                 directions[index] = 'L';
  30.                 numbers[index] = index + 1;
  31.                 Console.Write("{0}\t", numbers[index]);
  32.             }
  33.             Console.WriteLine();
  34.  
  35.             while (mobileNumber > 1)
  36.             {  
  37.                 int mobileNumberPosition = 0;
  38.                 while (true)
  39.                 {
  40.                     if (numbers[mobileNumberPosition] == mobileNumber)
  41.                     {
  42.                         break;
  43.                     }
  44.                     mobileNumberPosition++;
  45.                 }
  46.  
  47.                 if ((mobileNumberPosition == 0 && directions[mobileNumberPosition] == 'L') ||
  48.                     (mobileNumberPosition == (numberOfPermutations-1) && directions[numberOfPermutations-1] == 'R'))
  49.                 {
  50.                     mobileNumber--;
  51.                     continue;
  52.                 }
  53.                 else if (directions[mobileNumberPosition] == 'L' &&
  54.                     numbers[mobileNumberPosition] > numbers[mobileNumberPosition-1])
  55.                 {
  56.                     int numberBuffer = numbers[mobileNumberPosition];
  57.                     numbers[mobileNumberPosition] = numbers[mobileNumberPosition - 1];
  58.                     numbers[mobileNumberPosition - 1] = numberBuffer;
  59.  
  60.                     char directionBuffer = directions[mobileNumberPosition];
  61.                     directions[mobileNumberPosition] = directions[mobileNumberPosition - 1];
  62.                     directions[mobileNumberPosition - 1] = directionBuffer;
  63.                 }
  64.                 else if (directions[mobileNumberPosition] == 'R' &&
  65.                     numbers[mobileNumberPosition] > numbers[mobileNumberPosition + 1])
  66.                 {
  67.                     int buffer = numbers[mobileNumberPosition];
  68.                     numbers[mobileNumberPosition] = numbers[mobileNumberPosition + 1];
  69.                     numbers[mobileNumberPosition + 1] = buffer;
  70.  
  71.                     char directionBuffer = directions[mobileNumberPosition];
  72.                     directions[mobileNumberPosition] = directions[mobileNumberPosition + 1];
  73.                     directions[mobileNumberPosition + 1] = directionBuffer;
  74.                 }
  75.                 else
  76.                 {
  77.                     mobileNumber--;
  78.                     continue;
  79.                 }
  80.  
  81.                 for (int index = 0; index < numberOfPermutations; index++)
  82.                 {
  83.                     if (numbers[index] > mobileNumber)
  84.                     {
  85.                         if (directions[index] == 'L')
  86.                         {
  87.                             directions[index] = 'R';
  88.                         }
  89.                         else
  90.                         {
  91.                             directions[index] = 'L';
  92.                         }
  93.                     }
  94.                 }
  95.  
  96.                 for (int index = 0; index < numberOfPermutations; index++)
  97.                 {
  98.                     Console.Write("{0}\t", numbers[index]);
  99.                 }
  100.                 Console.WriteLine();
  101.                 mobileNumber = numberOfPermutations;
  102.             }
  103.  
  104.             //ouput
  105.         }
  106.     }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement