Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- namespace Permutations
- {
- class Program
- {
- static List<int> list = new List<int>() {1, 2, 3, 4 };
- static void Main(string[] args)
- {
- PrintPermutations(list, iterations: 40);
- Console.ReadKey();
- }
- public static void PrintPermutations(List<int> list, int iterations)
- {
- List<int> currentPermutation = list;
- Print(currentPermutation);
- for (int i = 0; i < iterations; i++)
- {
- Iterate(currentPermutation);
- Print(currentPermutation);
- }
- }
- /// <summary>
- /// Sets currentPermutation to the next permutation. This is done by arranging the numbers
- /// to create the lowest permutation that is still higher than the previous one. If there is
- /// no higher permutation, it arranges the numbers to create the lowest permutation.
- /// </summary>
- /// <param name="currentPermutation">The permutation to iterate.</param>
- private static void Iterate(List<int> currentPermutation)
- {
- // Find the spot to have a number inserted in, which is right before the last number that
- // is lower than the number after it. For example, for the permutation {2, 1, 5, 4, 3}, 1
- // is the last number that is lower than the number after it, 5, so the insertion spot
- // would be in front of the 1.
- bool foundInsertionIndex = false;
- int insertionIndex = 0;
- int numberToReplace = 0;
- for (int i = currentPermutation.Count - 2; i >= 0; i--)
- {
- if (currentPermutation[i] < currentPermutation[i + 1])
- {
- foundInsertionIndex = true;
- insertionIndex = i;
- numberToReplace = currentPermutation[insertionIndex];
- break;
- }
- }
- if (foundInsertionIndex)
- {
- // Find the lowest number that is located after numberToReplace and is higher than
- // numberToReplace. This is always the last number that is after and higher.
- // For the permutation {2, 1, 5, 4, 3} this would be 3.
- int replacerNumber = currentPermutation.Last(n => n > numberToReplace);
- // Move replacerNumber to the insertionIndex.
- // {2, 1, 5, 4, 3} becomes {2, 3, 1, 5, 4}
- currentPermutation.Remove(replacerNumber);
- currentPermutation.Insert(insertionIndex, replacerNumber);
- // Sort the numbers after the inserted number.
- // {2, 3, 1, 5, 4} becomes {2, 3, 1, 4, 5}
- currentPermutation.Sort(insertionIndex + 1, currentPermutation.Count - insertionIndex - 1, null);
- }
- else
- {
- // There are no insertion spots, so we reverse the permutation to start over again.
- currentPermutation.Reverse();
- }
- }
- private static void Print<T>(IEnumerable<T> list)
- {
- foreach (var a in list)
- {
- Console.Write(a.ToString());
- }
- Console.WriteLine();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment