Can you help me to find a way to randomize arrays? E.g.:
int[] arrayInt = { 1, 2, 3, 4, 5, 6, 7 };
after randomizing, the result should be stored in another array.
And when you randomize again it should be compared with the values stored in the second array, if that value exist the program must randomize again.
Here's an approach using Enumerable.OrderBy to order the input-array with a random variable. After the new sequence is generated it'll be compared with the input array with SequenceEqual:
public static T[] UniqueRandomArray<T>(T[] input, Random rnd)
{
if (input.Length <= 1) throw new ArgumentException("Input array must have at least two elements, otherwise the output would be the same.", "input");
IEnumerable<T> rndSeq;
while (input.SequenceEqual(rndSeq = input.OrderBy(x => rnd.Next())));
return rndSeq.ToArray();
}
This example-code generates 10 new arrays which are added to a List. It is ensured that the new array is different to the previous one:
Random rnd = new Random();
List<int[]> randomArrays = new List<int[]>();
int[] arrayInt1 = { 1, 2, 3, 4, 5, 6, 7 };
randomArrays.Add(arrayInt1);
for (int i = 0; i < 10; i++)
{
int[] lastArray = randomArrays[randomArrays.Count - 1];
int[] randomArray = UniqueRandomArray(lastArray, rnd);
randomArrays.Add(randomArray);
}
using linq
Random rand = new Random();
int[] arrayInt =
new[] {1, 2, 3, 4, 5, 6, 7}.Select(x => new {x, r = rand.Next()})
.OrderBy(x => x.r)
.Select(x => x.x)
.ToArray();
and you can randomize any type like this
public static class RandomExt
{
public static T[] RandomizeOrder<T>(this T[] array)
{
var rand = new Random();
return array.Select(x => new {x, r = rand.Next()})
.OrderBy(x => x.r)
.Select(x => x.x)
.ToArray();
}
}
int[] arrayInt = new[] {1, 2, 3, 4, 5, 6, 7}.RandomizeOrder();
First part of your question is about shuffling an array. A good algorithm is the Fisher-Yates shuffle.
The next part about comparing the result to the original is a bit more vague. I assume that you want to create a random shuffle that guarantees that all elements are shuffled to a new position. E.g.
I have created some extensions for doing this (note that this is a generic solution with element type T):
static class EnumerableExtensions {
static Random random = new Random();
public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source) {
var list = source.ToList();
for (var k = 0; k < list.Count; k += 1) {
var j = random.Next(k, list.Count);
Swap(list, k, j);
}
return list;
}
public static IEnumerable<T> RandomizeUniquely<T>(this IEnumerable<T> source) {
while (true) {
var randomized = source.Randomize();
var isNotUnique = source
.Zip(randomized, (a, b) => Equals(a, b))
.Any(equal => equal);
if (!isNotUnique)
return randomized;
}
}
static void Swap<T>(IList<T> list, Int32 i, Int32 j) {
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
The Randomize method implements the Fisher-Yates shuffle. The RandomizeUniquely uses this method and tries to create a shuffle that satifies the condition described above. The method simply tries until a satisfactory shuffle is found. Note that this algorithm may not terminate. E.g. if the source only has one element no unique shuffle can be found. Also, if the source contains duplicates a solution may not exist.
To use the method simply call it like this:
var randomized = Enumerable.Range(1, 7).RandomizeUniquely();
The code can be improved by validating parameters and deciding how to handle the non-termination problem described above.
Hope this helps. Uses a secure crypto provider and a secure hash for the comparison - overkill, so feel free to adjust the providers used :)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.Collections;
using System.Collections.Concurrent;
namespace RandomiseArray
{
static class Program
{
static void Main(string[] args)
{
// source array
string[] s = new string[] { "a", "b", "c", "d", "e", "f", "g" };
// number of unique random combinations required
int combinationsRequired = 5;
var randomCombinations = s.Randomise(System.Text.UnicodeEncoding.Unicode.GetBytes, combinationsRequired);
foreach (var c in randomCombinations)
Console.WriteLine(c.Aggregate((x, y) => x + "," + y));
Console.ReadLine();
}
/// <summary>
/// given a source array and a function to convert any item in the source array to a byte array, produce x unique random sequences
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source"></param>
/// <param name="byteFunction"></param>
/// <param name="x"></param>
/// <returns></returns>
public static IEnumerable<IEnumerable<T>> Randomise<T>(this IEnumerable<T> source, Func<T, byte[]> byteFunction, int x)
{
var foundValues = new ConcurrentDictionary<byte[], T[]>();
int found = 0;
do
{
T[] y = source.Randomise().ToArray();
var h = y.Hash(byteFunction);
if (!foundValues.Keys.Contains(h))
{
found++;
foundValues[h] = y;
yield return y; // guaranteed unique combination (well, within the collision scope of SHA512...)
}
} while (found < x);
}
public static IEnumerable<T> Randomise<T>(this IEnumerable<T> source)
{
using (RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider())
return source.OrderBy(i => rng.Next());
}
public static int Next(this RNGCryptoServiceProvider rng)
{
byte[] buf = new byte[4];
rng.GetBytes(buf);
return BitConverter.ToInt32(buf, 0);
}
public static byte[] Hash<T>(this IEnumerable<T> items, Func<T, byte[]> getItemBytes)
{
using (SHA512CryptoServiceProvider sha = new SHA512CryptoServiceProvider())
return sha.ComputeHash(items.SelectMany(i => getItemBytes(i)).ToArray());
}
}
}
OrderBy is nice way to shuffle, but it uses sorting which is O(n log n). Shuffle can be done in O(n).
Here is pseudo code from wikipedia
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
