Случайный массив целых чисел

Question

Можете ли вы помочь мне найти способ рандомизации массивов? Например:

int[] arrayInt = { 1, 2, 3, 4, 5, 6, 7 }; 

после рандомизации результат должен храниться в другом массиве.

И если вы рандомизируете снова, его следует сравнить со значениями, хранящимися во втором массиве, если это значение существует, программа должна снова рандомизироваться.

Answer 1

Вот подход с использованием Enumerable.OrderBy для заказа входного массива с переменной random. После того, как новая последовательность генерируется он будет по сравнению с входного массива с 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(); 
} 

Этот пример кода генерирует 10 новых массивов, которые добавляются в список. Он заверил, что новый массив отличается от предыдущего:

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); 
} 

Demo

Answer 2

с помощью 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(); 

и вы можете рандомизации любого типа, как это

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(); 

Answer 3

Первая часть вашего вопроса - перетасовка массива. Хорошим алгоритмом является Fisher-Yates shuffle.

Следующая часть о сравнении результата с оригиналом несколько более смутная. Я предполагаю, что вы хотите создать случайную перетасовку, которая гарантирует, что все элементы перетасовываются в новую позицию. Например.

• [0, 1, 2] => [1, 2, 0] в порядке, но
• [0, 1, 2] => [2, 1, 0] не в порядке, потому что 1 остается вместо

Я создал несколько расширений для этого (заметим, что это общее решение с элементом типа 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; 
    } 

} 

метод Randomize реализует перетасовать Fisher-Yates. RandomizeUniquely использует этот метод и пытается создать перетасовку, которая удовлетворяет описанному выше условию. Метод просто пытается до тех пор, пока не будет найдено удовлетворительное перемещение. Обратите внимание, что этот алгоритм не может завершиться. Например. если источник имеет только один элемент, то не может быть найдена уникальная тасовка. Кроме того, если источник содержит дубликаты, решение может не существовать.

Чтобы использовать метод просто назвать это так:

var randomized = Enumerable.Range(1, 7).RandomizeUniquely(); 

Код может быть улучшена путем проверки параметров и решить, как справиться с этой проблемой без прекращения описанной выше.

Answer 4

Надеюсь, это поможет.Использование безопасного поставщика криптографического и безопасный хэш для сравнения - избыточно, так что не стесняйтесь, чтобы настроить поставщик используемых :)

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()); 
     } 
    } 
} 

Answer 5

OrderBy это хороший способ перетасовать, но он использует сортировку, которая является O (п § п). Перемешать можно в O (n).

Вот псевдокод из wikipedia

for i from n − 1 downto 1 do 
     j ← random integer with 0 ≤ j ≤ i 
     exchange a[j] and a[i]