Вот фон для этого вопроса. Мы с друзьями играли в игру, где каждый должен сделать подарок другим людям. Для того, чтобы определить, кто кому должен подарить подарок, мы решили провести жеребьевку. Но проблема в том, что кто-то может в итоге подарить себе подарки, что не смешно. Вы можете видеть, что ожидаемое количество таких несчастных людей равно 1, так что это происходит довольно часто.
Для этого, кажется, отлично подходит разладка. Если я действительно могу создать разладку, тогда я могу просто выбрать одну разладку и использовать ее, чтобы решить, кто кому дарит подарки.
Генерация рандомизированных смещений может быть выполнена методом Лас-Вегаса. Но проблема в том, что он ожидал только полиномиального времени выполнения. Вот и я пришел к этой проблеме поиска i-й разладки. Если я могу случайным образом выбрать i в [1, D_n] и использовать некоторый алгоритм (эффективный) для полиномиального времени для наихудшего случая, чтобы получить i-ю разладку, то это сделано.
источник
Ответы:
На самом деле это может быть хорошим вопросом, но он плохо сформулирован в его нынешнем виде. Хорошо известные алгоритмы генерации случайных отклонений имеют ожидаемое линейное время, но, возможно, проблема в том, чтобы найти алгоритм полиномиального времени для наихудшего случая.
См. Например: http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (и слайды: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf ).
источник
Почему бы не для каждой позиции i случайно выбрать из всех элементов, кроме i ? Например, вы можете выбрать индекс в исходный массив из [0..n-2] , и если вы получите j> = i, вы будете использовать j + 1 .
источник