Перемешать случайным образом массив целых чисел

@NJohn · Регистрация: 14.07.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте!
Подскажите, пожалуйста, как в C# перемешать случайным образом массив целых чисел.
Аналог random.shuffle(lst) в Python.
Спасибо!

@DataPlanner · 26.11.2013, 03:18

В шарпе тоже есть Random.Next

@NJohn · 26.11.2013, 11:22 **[ТС]**

Это я нашел. А встроенной функции перемешивания нету?
Вот моя реализация:

C#

        public static void Shuffle(this int[] array)
        {
            if (array.Length < 1) return;
            var random = new Random();
            for (var i = 0; i < array.Length; i++)
            {
                var key = array[i];
                var rnd = random.Next(i, array.Length);
                array[i] = array[rnd];
                array[rnd] = key;
            }
        }

@DataPlanner · 26.11.2013, 11:32

встроенной функции перемешивания нет

@Diman777 · 26.11.2013, 11:38

Сообщение от NJohn

как в C# перемешать случайным образом массив целых чисел.

C#

1	OrderBy(x => rand.Next())

@DataPlanner · 26.11.2013, 11:42

Сообщение от Diman777

OrderBy(x => rand.Next())

Красиво!

@NJohn · 26.11.2013, 11:54 **[ТС]**

Diman777, спасибо!

@kolorotur · 26.11.2013, 12:13

O(n) с гарантированной сменой позиции каждого элемента:

C#

var r = new Random();
for (int i = arr.Length - 1; i > 0; i--)
{
   int j = r.Next(i);
   var t = arr[i];
   arr[i] = arr[j];
   arr[j] = t;
}

@NJohn · 26.11.2013, 15:52 **[ТС]**

kolorotur, спасибо!
Но у меня по-моему тоже самое

@kolorotur · 26.11.2013, 17:23

Сообщение от NJohn

Но у меня по-моему тоже самое

Ага, оно

Можно, конечно, придраться к тому, что последний элемент сам с собой свопнется, но это чепуха.

@NJohn · 26.11.2013, 20:40 **[ТС]**

kolorotur, спасибо за замечание!
Действительно, так оно и есть.
Поставил условие i < array.Length-1

@rattrapper · 09.05.2015, 23:34

Сообщение от kolorotur

с гарантированной сменой позиции каждого элемента

на самом деле, это не всегда хорошо. теряется солидная доля перестановок, я насчитал (n - 1)! перестановок вместо n! . для малых n - это критично, например 4! = 24 вместо 5! = 120 для n = 5. благо, исправить несложно - заменив 4-ю строку

C#

1	int j = r.Next(i + 1);

@kolorotur · 10.05.2015, 00:55

Сообщение от rattrapper

на самом деле, это не всегда хорошо.

Почему же не хорошо, если стоит задача — перемешать?

Сообщение от rattrapper

теряется солидная доля перестановок, я насчитал (n - 1)! перестановок вместо n!

Тут важно понимать: в чем цель алгоритма.
Если цель в генерации как можно большего количества возможных комбинаций, то да — здесь не поспоришь.
Если же цель состоит в перемешивании массива и надо допустить возможность того, что какие-то из элементов могут остаться на своих местах, то нужно определить предел этому количеству. 1? 2? n/2? n? Последний вариант — это отсутствие перемешивания, т.к. конечная пермутация является идентичностью.
Потому если цель состоит в перемешивании, то лучше смириться с потерей некоторого количества пермутаций в обмен на гарантию того, что в итоге не получим идентичность.
Ну или значительно усложнять алгоритм для учета количества элементов, которым можно оставаться на местах.

Вы когда колоду карт тасуете, вам что важнее: какое количество уникальных раскладов вы можете теоретически получить или то, что у вас колода после перетасовки не будет такой же, как до?

Сообщение от rattrapper

для малых n - это критично

Для малых n как раз более критична гарантия перестановки, т.к. если у вас множество { 1, 2 }, то при выбранном вами подходе мы либо имеем перестановку, либо идентичность: 50/50.
Если нужно перемешивание, то меня расклад фифти-фифти ну никак не устраивает

Сообщение от rattrapper

благо, исправить несложно - заменив 4-ю строку

Тем самым сведя на нет весь замысел — гарантию того, что массив перемешается

@rattrapper · 10.05.2015, 01:40

kolorotur, ну тут спорить не о чем, все зависит о поставления задачи. Вы ведь не будете не будете заведомо исключать комбинацию( 1 2 3 4) из лотерейных билетов, не говоря уже про (3 2 4 1).
Кстати, питоновский random.shuffle, упомянутый в шапке, мешает рандомно без каких-либо ограничений.

@kolorotur · 10.05.2015, 01:58

Сообщение от rattrapper

Вы ведь не будете не будете заведомо исключать комбинацию( 1 2 3 4) из лотерейных билетов, не говоря уже про (3 2 4 1).

Так я о том же: есть перемешивание — это получение одной пермутации из другой, а есть генерирование случайной/уникальной пермутации. Они хоть и похожи, но по сути разные вещи и выполняют разные задачи.

Сообщение от rattrapper

Кстати, питоновский random.shuffle, упомянутый в шапке, мешает рандомно без каких-либо ограничений.

Плохой значит этот shuffle.
Но хоть какой-то, конечно, лучше, чем никакого.

@_exp10der_ · 10.05.2015, 02:02

Чем перемешивание отличается от случайной перестановки?

@kolorotur · 10.05.2015, 02:34

Сообщение от _exp10der_

Чем перемешивание отличается от случайной перестановки?

Тем, что идентичность перестановки является случайной перестановкой, но не является перемешиванием.
Очевидно же.

@_exp10der_ Warrior 500 / 427 / 177 Регистрация: 23.11.2014 Сообщений: 932
	10.05.2015, 02:02	16
	Чем перемешивание отличается от случайной перестановки? 0

@NJohn 4 / 4 / 2 Регистрация: 14.07.2011 Сообщений: 19
		1
	Перемешать случайным образом массив целых чисел 26.11.2013, 00:59. Показов 18701. Ответов 16 Метки нет (Все метки) Здравствуйте! Подскажите, пожалуйста, как в C# перемешать случайным образом массив целых чисел. Аналог random.shuffle(lst) в Python. Спасибо! 0

@DataPlanner 158 / 187 / 48 Регистрация: 25.11.2013 Сообщений: 978
	26.11.2013, 03:18	2
	В шарпе тоже есть Random.Next 0

@DataPlanner 158 / 187 / 48 Регистрация: 25.11.2013 Сообщений: 978
	26.11.2013, 11:32	4
	встроенной функции перемешивания нет 0

@DataPlanner 158 / 187 / 48 Регистрация: 25.11.2013 Сообщений: 978
	26.11.2013, 11:42	6
	Сообщение от Diman777 OrderBy(x => rand.Next()) Красиво! 0

@NJohn 4 / 4 / 2 Регистрация: 14.07.2011 Сообщений: 19
	26.11.2013, 11:54 [ТС]	7
	Diman777, спасибо! 0

@NJohn 4 / 4 / 2 Регистрация: 14.07.2011 Сообщений: 19
	26.11.2013, 15:52 [ТС]	9
	kolorotur, спасибо! Но у меня по-моему тоже самое 0

@kolorotur 17437 / 12829 / 3361 Регистрация: 17.09.2011 Сообщений: 21,107
	26.11.2013, 17:23	10
	Сообщение от NJohn Но у меня по-моему тоже самое Ага, оно Можно, конечно, придраться к тому, что последний элемент сам с собой свопнется, но это чепуха. 0

@NJohn 4 / 4 / 2 Регистрация: 14.07.2011 Сообщений: 19
	26.11.2013, 20:40 [ТС]	11
	kolorotur, спасибо за замечание! Действительно, так оно и есть. Поставил условие i < array.Length-1 0

@kolorotur 17437 / 12829 / 3361 Регистрация: 17.09.2011 Сообщений: 21,107
	10.05.2015, 00:55	13
	Сообщение от rattrapper на самом деле, это не всегда хорошо. Почему же не хорошо, если стоит задача — перемешать? Сообщение от rattrapper теряется солидная доля перестановок, я насчитал (n - 1)! перестановок вместо n! Тут важно понимать: в чем цель алгоритма. Если цель в генерации как можно большего количества возможных комбинаций, то да — здесь не поспоришь. Если же цель состоит в перемешивании массива и надо допустить возможность того, что какие-то из элементов могут остаться на своих местах, то нужно определить предел этому количеству. 1? 2? n/2? n? Последний вариант — это отсутствие перемешивания, т.к. конечная пермутация является идентичностью. Потому если цель состоит в перемешивании, то лучше смириться с потерей некоторого количества пермутаций в обмен на гарантию того, что в итоге не получим идентичность. Ну или значительно усложнять алгоритм для учета количества элементов, которым можно оставаться на местах. Вы когда колоду карт тасуете, вам что важнее: какое количество уникальных раскладов вы можете теоретически получить или то, что у вас колода после перетасовки не будет такой же, как до? Сообщение от rattrapper для малых n - это критично Для малых n как раз более критична гарантия перестановки, т.к. если у вас множество { 1, 2 }, то при выбранном вами подходе мы либо имеем перестановку, либо идентичность: 50/50. Если нужно перемешивание, то меня расклад фифти-фифти ну никак не устраивает Сообщение от rattrapper благо, исправить несложно - заменив 4-ю строку Тем самым сведя на нет весь замысел — гарантию того, что массив перемешается 0

@rattrapper foo(); 886 / 587 / 222 Регистрация: 03.07.2013 Сообщений: 1,549 Записей в блоге: 2
	10.05.2015, 01:40	14
	kolorotur, ну тут спорить не о чем, все зависит о поставления задачи. Вы ведь не будете не будете заведомо исключать комбинацию( 1 2 3 4) из лотерейных билетов, не говоря уже про (3 2 4 1). Кстати, питоновский random.shuffle, упомянутый в шапке, мешает рандомно без каких-либо ограничений. 0

	10.05.2015, 02:34

Опции темы

@kolorotur 17437 / 12829 / 3361 Регистрация: 17.09.2011 Сообщений: 21,107
	10.05.2015, 01:58	15
	Сообщение от rattrapper Вы ведь не будете не будете заведомо исключать комбинацию( 1 2 3 4) из лотерейных билетов, не говоря уже про (3 2 4 1). Так я о том же: есть перемешивание — это получение одной пермутации из другой, а есть генерирование случайной/уникальной пермутации. Они хоть и похожи, но по сути разные вещи и выполняют разные задачи. Сообщение от rattrapper Кстати, питоновский random.shuffle, упомянутый в шапке, мешает рандомно без каких-либо ограничений. Плохой значит этот shuffle. Но хоть какой-то, конечно, лучше, чем никакого. 0

@kolorotur 17437 / 12829 / 3361 Регистрация: 17.09.2011 Сообщений: 21,107
	10.05.2015, 02:34	17
	Сообщение от _exp10der_ Чем перемешивание отличается от случайной перестановки? Тем, что идентичность перестановки является случайной перестановкой, но не является перемешиванием. Очевидно же. 0