Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- namespace Example
- {
- class Program
- {
- public static void Main(string[] args)
- {
- const int length = 3;
- const int cycles = 1000000;
- Random r = new Random();
- List<int[]> permutations = new List<int[]>();
- // Build all the permutations
- {
- var numbers = new int[length];
- Reset(numbers);
- // We calculate all the possible permutations. We will use them
- // later, to see if each one happens the same number of times
- permutations.Add((int[])numbers.Clone());
- while (!NextPermutation(numbers))
- {
- permutations.Add((int[])numbers.Clone());
- }
- }
- Calculate("Fisher-Yates backward", length, cycles, permutations.AsReadOnly(), nums => Shuffle1(nums, r));
- Calculate("Fisher-Yates forward", length, cycles, permutations.AsReadOnly(), nums => Shuffle2(nums, r));
- Calculate("Naive", length, cycles, permutations.AsReadOnly(), nums => NaiveShuffle(nums, r));
- Calculate("r.Next()", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next()));
- Calculate("r.Next(int.MaxValue)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(int.MaxValue)));
- Calculate("r.Next(1)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(1)));
- Calculate("r.Next(2)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(2)));
- Calculate("r.Next(4)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(4)));
- Calculate("r.Next(8)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(8)));
- Calculate("r.Next(16)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(16)));
- Calculate("r.Next(32)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(32)));
- Calculate("r.Next(64)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(64)));
- Calculate("r.Next(128)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(128)));
- Calculate("r.Next(256)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(256)));
- Calculate("r.Next(512)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(512)));
- Calculate("r.Next(1024)", length, cycles, permutations.AsReadOnly(), nums => WithOrderBy(nums, () => r.Next(1024)));
- }
- #region Algorithms
- // http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- public static void Shuffle1<T>(T[] array, Random r)
- {
- // Shuffles in place! Compatible with arrays (but a little
- // slower, because it is using the IList<T> interface instead of
- // using direct array accessors)
- // Using the backward algorithm of the Wiki.
- // With C# I could have used the forward algorithm.
- for (int i = array.Length - 1; i > 0; i--)
- {
- int j = r.Next(i + 1);
- T temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- }
- // http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- public static void Shuffle2<T>(T[] array, Random r)
- {
- // Shuffles in place! Compatible with arrays (but a little
- // slower, because it is using the IList<T> interface instead of
- // using direct array accessors)
- // Using the forward algorithm of the Wiki.
- for (int i = 0; i < array.Length; i++)
- {
- int j = r.Next(i, array.Length);
- T temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- }
- // Taken from http://blog.codinghorror.com/the-danger-of-naivete/
- public static void NaiveShuffle<T>(T[] array, Random r)
- {
- for (int i = 0; i < array.Length; i++)
- {
- int j = r.Next(array.Length);
- T temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- }
- // OrderBy shuffler, receives a function orderer that should be
- // something like () => r.Next()
- public static void WithOrderBy<T>(T[] array, Func<int> orderer)
- {
- var enu = array.OrderBy(x => orderer());
- // OrderBy creates a new "collection". We have to overwrite the
- // old one
- int i = 0;
- foreach (T el in enu)
- {
- array[i] = el;
- i++;
- }
- }
- #endregion
- // Taken from http://stackoverflow.com/questions/11208446/generating-permutations-of-a-set-most-efficiently
- public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
- {
- // More efficient to have a variable instead of accessing a property
- var count = elements.Length;
- // Indicates whether this is the last lexicographic permutation
- var done = true;
- // Go through the array from last to first
- for (var i = count - 1; i > 0; i--)
- {
- var curr = elements[i];
- // Check if the current element is less than the one before it
- if (curr.CompareTo(elements[i - 1]) < 0)
- {
- continue;
- }
- // An element bigger than the one before it has been found,
- // so this isn't the last lexicographic permutation.
- done = false;
- // Save the previous (bigger) element in a variable for more efficiency.
- var prev = elements[i - 1];
- // Have a variable to hold the index of the element to swap
- // with the previous element (the to-swap element would be
- // the smallest element that comes after the previous element
- // and is bigger than the previous element), initializing it
- // as the current index of the current item (curr).
- var currIndex = i;
- // Go through the array from the element after the current one to last
- for (var j = i + 1; j < count; j++)
- {
- // Save into variable for more efficiency
- var tmp = elements[j];
- // Check if tmp suits the "next swap" conditions:
- // Smallest, but bigger than the "prev" element
- if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
- {
- curr = tmp;
- currIndex = j;
- }
- }
- // Swap the "prev" with the new "curr" (the swap-with element)
- elements[currIndex] = prev;
- elements[i - 1] = curr;
- // Reverse the order of the tail, in order to reset it's lexicographic order
- for (var j = count - 1; j > i; j--, i++)
- {
- var tmp = elements[j];
- elements[j] = elements[i];
- elements[i] = tmp;
- }
- // Break since we have got the next permutation
- // The reason to have all the logic inside the loop is
- // to prevent the need of an extra variable indicating "i" when
- // the next needed swap is found (moving "i" outside the loop is a
- // bad practice, and isn't very readable, so I preferred not doing
- // that as well).
- break;
- }
- // Return whether this has been the last lexicographic permutation.
- return done;
- }
- // Reset an array to a sequence 0... array.Length - 1
- public static void Reset(int[] array)
- {
- for (int i = 0; i < array.Length; i++)
- {
- array[i] = i;
- }
- }
- // Simple array IEqualityComparer
- public class ArrayComparer : IEqualityComparer<int[]>, IComparer<int[]>
- {
- public static readonly ArrayComparer Instance = new ArrayComparer();
- protected ArrayComparer()
- {
- }
- public bool Equals(int[] x, int[] y)
- {
- return Compare(x, y) == 0;
- }
- public int GetHashCode(int[] obj)
- {
- unchecked
- {
- int hash = 17;
- if (obj != null)
- {
- for (int i = 0; i < obj.Length; i++)
- {
- hash = hash * 23 + obj[i].GetHashCode();
- }
- }
- return hash;
- }
- }
- public int Compare(int[] x, int[] y)
- {
- if (x == null)
- {
- if (y == null)
- {
- return 0;
- }
- return -1;
- }
- if (y == null)
- {
- return 1;
- }
- int min = Math.Min(x.Length, y.Length);
- for (int i = 0; i < min; i++)
- {
- int cmp = x[i].CompareTo(y[i]);
- if (cmp != 0)
- {
- return cmp;
- }
- }
- return x.Length.CompareTo(y.Length);
- }
- }
- // Executes cycles shuffles on a int[length] array, using shuffler.
- // Shows the number of times each of the permutations happened, with
- // a comparison to the first of the permutations
- public static void Calculate(string title, int length, int cycles, IReadOnlyList<int[]> permutations, Action<int[]> shuffler)
- {
- var numbers = new int[length];
- Reset(numbers);
- var dict = permutations.ToDictionary(x => x, x => 0, ArrayComparer.Instance);
- for (int i = 0; i < cycles; i++)
- {
- Reset(numbers);
- shuffler(numbers);
- dict[numbers]++;
- }
- Console.WriteLine(title);
- var dict2 = dict.OrderBy(x => x.Key, ArrayComparer.Instance).ToArray();
- // All the % are based on the first element
- foreach (var kv in dict2)
- {
- Console.WriteLine("[{0}]: {1} ({2:P2})", string.Join(",", kv.Key), kv.Value, ((double)kv.Value) / dict2[0].Value - 1);
- }
- Console.WriteLine();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement