Guest User

Looping Permutations

a guest
Nov 22nd, 2011
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.25 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace Permutations
  7. {
  8.    class Program
  9.    {
  10.       static List<int> list = new List<int>() {1, 2, 3, 4 };
  11.  
  12.       static void Main(string[] args)
  13.       {        
  14.          PrintPermutations(list, iterations: 40);        
  15.          Console.ReadKey();
  16.       }
  17.            
  18.       public static void PrintPermutations(List<int> list, int iterations)
  19.       {
  20.          List<int> currentPermutation = list;
  21.          Print(currentPermutation);
  22.  
  23.          for (int i = 0; i < iterations; i++)
  24.          {
  25.             Iterate(currentPermutation);
  26.             Print(currentPermutation);
  27.          }      
  28.       }
  29.  
  30.       /// <summary>
  31.       /// Sets currentPermutation to the next permutation.  This is done by arranging the numbers
  32.       /// to create the lowest permutation that is still higher than the previous one.  If there is
  33.       /// no higher permutation, it arranges the numbers to create the lowest permutation.
  34.       /// </summary>
  35.       /// <param name="currentPermutation">The permutation to iterate.</param>
  36.       private static void Iterate(List<int> currentPermutation)
  37.       {
  38.          // Find the spot to have a number inserted in, which is right before the last number that
  39.          // is lower than the number after it. For example, for the permutation {2, 1, 5, 4, 3}, 1
  40.          // is the last number that is lower than the number after it, 5, so the insertion spot
  41.          // would be in front of the 1.
  42.          bool foundInsertionIndex = false;
  43.          int insertionIndex = 0;
  44.          int numberToReplace = 0;
  45.  
  46.          for (int i = currentPermutation.Count - 2; i >= 0; i--)
  47.          {
  48.             if (currentPermutation[i] < currentPermutation[i + 1])
  49.             {
  50.                foundInsertionIndex = true;
  51.                insertionIndex = i;
  52.                numberToReplace = currentPermutation[insertionIndex];
  53.                break;
  54.             }
  55.          }
  56.  
  57.          if (foundInsertionIndex)
  58.          {
  59.             // Find the lowest number that is located after numberToReplace and is higher than
  60.             // numberToReplace. This is always the last number that is after and higher.
  61.             // For the permutation {2, 1, 5, 4, 3} this would be 3.
  62.             int replacerNumber = currentPermutation.Last(n => n > numberToReplace);
  63.  
  64.             // Move replacerNumber to the insertionIndex.
  65.             // {2, 1, 5, 4, 3} becomes {2, 3, 1, 5, 4}
  66.             currentPermutation.Remove(replacerNumber);
  67.             currentPermutation.Insert(insertionIndex, replacerNumber);            
  68.  
  69.             // Sort the numbers after the inserted number.
  70.             // {2, 3, 1, 5, 4} becomes {2, 3, 1, 4, 5}
  71.             currentPermutation.Sort(insertionIndex + 1, currentPermutation.Count - insertionIndex - 1, null);
  72.          }
  73.          else
  74.          {
  75.             // There are no insertion spots, so we reverse the permutation to start over again.
  76.             currentPermutation.Reverse();
  77.          }  
  78.       }    
  79.  
  80.       private static void Print<T>(IEnumerable<T> list)
  81.       {
  82.          foreach (var a in list)
  83.          {
  84.             Console.Write(a.ToString());
  85.          }
  86.          Console.WriteLine();
  87.       }
  88.    }
  89. }
  90.  
  91.  
  92.  
Advertisement
Add Comment
Please, Sign In to add comment