Алгоритм генерации случайного порядка элементов

Как рандомизировать порядка примерно 20 элементов с наименьшей сложностью? (генерируя случайные перестановки)

 Ante07 нояб. 2009 г., 02:57
приблизительно равняется
 ThisSuitIsBlackNot07 нояб. 2009 г., 03:00
ca. а такжеCCA. оба сокращения дляоколо, хотяоколо используется только для ссылки на даты:en.wikipedia.org/wiki/Circa
 Murali VP07 нояб. 2009 г., 02:49
Канонический корреляционный анализ?
 Mathias07 нояб. 2009 г., 03:28
Isn»Это дубликат списка вопросов в случайном порядке?stackoverflow.com/questions/375351/...
 Stefan Kendall07 нояб. 2009 г., 02:51
Что вы подразумеваете под ок. :П
 Stefan Kendall07 нояб. 2009 г., 02:48
Что вы подразумеваете под CCA?
 Ante07 нояб. 2009 г., 02:58
подробнее об этомfreebase.com/view/en/circa

Ответы на вопрос(4)

Простой способ рандомизировать порядок - создать новый список правильного размера (20 в вашем случае), выполнить итерацию по первому списку и добавить каждый элемент в произвольной позиции во второй список. Если случайная позиция уже заполнена, поместите ее в следующую свободную позицию.

Я думаю, что этот псевдокод правильный:

list newList
foreach (element in firstList)
    int position = Random.Int(0, firstList.Length - 1)
    while (newList[position] != null)
        position = (position + 1) % firstList.Length
    newList[position] = element

РЕДАКТИРОВАТЬ: так получается, что этот ответ нена самом деле это хорошо. Это не особенно быстро и не случайно. Спасибо за ваши Коментарии. Для хорошего ответа, пожалуйста, вернитесь к началу страницы :-)

 Bruno Reis07 нояб. 2009 г., 03:23
В худшем случае это алгоритм O (n ^ 2) (т. Е. Если ваш генератор случайных чисел говорит "1, 1, 1, 1, 1, 1, 1, ... "Позволь подсчитать остальное), не очень оптимизировано.
 Guffa07 нояб. 2009 г., 04:00
Помещение предметов в следующую свободную позицию делает его менее случайным. Предметы сохранят свой первоначальный порядок больше, чем в случайном порядке. Чтобы исправить это, вам нужно будет выбрать новую случайную позицию, когда позиция будет занята, что, конечно, делает ее намного медленнее.
 David Johnstone07 нояб. 2009 г., 04:19
Тот'Хороший вопрос, Хаффа. Я'Я никогда не осознавал этого. Благодарю. По крайней мере ямы кое-что узнали здесь :-)

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

Генерация случайного списка int в F #

Равномерно распределенный случайный список перестановок в F #

В первом посте я исследую некоторые возможности и, наконец, получаюфункция для случайной перестановки общего списка со сложностью O (n), должным образом инкапсулированный для работы с неизменяемыми данными (т. е. без побочных эффектов).

Во втором посте я делаю его равномерно распределенным.

Код на F #, я надеюсь, что вы нене возражаю!

Удачи.

РЕДАКТИРОВАТЬ: Я неУ меня нет формального доказательства, но интуиция подсказывает мне, что сложность такого алгоритма не может быть нижеНа), Я'Буду очень признателен за то, чтобы сделать это быстрее!

 Ante07 нояб. 2009 г., 03:09
рекурсия во второй статье проста ... я думаю, что я мог бы использовать это ..
 Steve Jessop07 нояб. 2009 г., 04:25
Все перестановки должны быть возможны, и перестановка массива в расстройство (то есть перестановкаp для которогоp(k) != k для всехk) требует, чтобы каждый элемент был посещен. Отсюда O (n) в худшем случае. Или это все еще не достаточно формально?
 Steve Jessop07 нояб. 2009 г., 04:27
Кроме того, O (n) средний случай с тем же доказательством, подумайте об этом, так как IIRC доля перестановок (1 ... n), которые являются нарушениями, приближается к 1 / e, когда n приближается к бесконечности.

Возможно, кто-то уже реализовал тасование для вас. Например, в Python вы можете использоватьrandom.shuffleв C ++random_shuffleи в PHP.shuffle

 Roberto Bonvallet07 нояб. 2009 г., 15:08
Удивительно, но в PHP это называетсяshuffle :) яуточню мой ответ.
 Ante07 нояб. 2009 г., 04:07
хм .. php может быть?
Решение Вопроса
 SourceOverflow30 окт. 2017 г., 12:37
Ну, я разочарован, что это ответ. Поскольку сначала нужно выполнить итерацию по списку, чтобы заполнить его, а затем перетасовать (по общепризнанно хорошему алгоритму), я бы подумал, что есть лучшее решение.
 Steve Jessop07 нояб. 2009 г., 04:31
Разочаровывает, что кто-то сказал что-то еще, честно говоря.

Ваш ответ на вопрос