Как перемешать (случайно переставить) элементы в массиве?

#c_sharp

Есть данные, записанные в массив или генерируемые на лету. Как можно получить их
случайную перестановку в массиве или другом контейнере?

Например: как можно получить случайную перестановку чисел от 1 до n в массиве/списке?
    

Ответы

Ответ 1

Если у вас уже есть набор данных (массив или List), скорее всего вам нужно перемешивание
его «на месте». Для этого подойдёт алгоритм из 3.4.2P из TAOCP, известный также как
Fisher–Yates shuffle.

Пусть ваши данные находятся в массиве T[] data. Пусть random — экземпляр типа Random*.
Тогда для перемешивания подходит следующий код:

for (int i = data.Length - 1; i >= 1; i--)
{
   int j = random.Next(i + 1);
   // обменять значения data[j] и data[i]
   var temp = data[j];
   data[j] = data[i];
   data[i] = temp;
}


Код очевидным образом адаптируется для случая List.



Для случая, когда вам нужна не перетасовка на месте, а заполнение данными из другого
источника, или данные генерируются на ходу (например, вы хотите получить перестановку
чисел 1...n), можно воспользоваться немного модифицированным алгоритмом.

Если количество данных известно заранее (пусть это будет n), делаем так:

data = new T[n];
for (int i = 0; i < n; i++)
{
    int j = random.Next(i + 1);
    if (j != i)
        data[i] = data[j];
    data[j] = generate(i);
}


Здесь generate(i) — выражение, которое даёт следующий, i-ый член исходной последовательности.
Например, если данные поступают из массива source, то generate(i) — это просто source[i].
Если вы перемешиваете числа от 1 до n, это просто i + 1, и т. д.

Для случая, когда количество элементов не известно заранее (например, из произвольного
IEnumerable), подойдёт следующая модификация. Наш целевой контейнер должен быть
List, чтобы его можно было динамически увеличивать.

data = new List();
foreach (var s in source)
{
    int j = random.Next(data.Length + 1);
    if (j == data.Count)
    {
        data.Add(s);
    }
    else
    {
        data.Add(data[j]);
        data[j] = s;
    }
}


Код основан на цитированной статье из Википедии.



*Не стоит создавать новый экземпляр Random каждый раз при выполнении этого алгоритма:
это даёт большие шансы, что два раза подряд сгенерированная перестановка будет фактически
одинаковой. Если ваша программа однопоточная, лучше всего создать единственный статический
экземпляр Random в начале программы, и использовать его.


Ответ 2

На взрослом https://stackoverflow.com/questions/273313/randomize-a-listt

Там победитель алгоритм, тот, что привел VladD

private static Random rng = new Random((int) DateTime.Now.Ticks & 0x0000FFFF);


public static void Shuffle(this IList list)  
{  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}


Можно вспомнить БД

items.Select(i=> new {I=i, sort= Guid.NewGuid()}).OrderBy (i =>i.sort).Select(i=>i.I);

items.Select(i=> new {I=i, sort= rng.Next()}).OrderBy (i =>i.sort).Select(i=>i.I);


Ответ 3

не хочешь использовать Guid.NewGuid().ToString() для случайной сортировки?
var lstResult = yourList.OrderBy(x => Guid.NewGuid().ToString()).ToList();