CD
Если n=k+1, то из первого множества всегда будет на один элемент больше. Это не позволяет получить любой такой список.
Товарищ не указал, что ему нужна строгая равномерность
Size: a a a
2020 June 27
CD
В частности, его решение очевидно этим свойством не обладает :)
CD
Как, вроде бы, и все предложенные
DU
Поэтому и надо уточнить. Так-то детерминированный список -- тоже в некотором роде случайный.
CD
какая модель?
^
JM
Поэтому и надо уточнить. Так-то детерминированный список -- тоже в некотором роде случайный.
Окей, нужен алгоритм, который может сгенерировать любой из удовлетворяющих условию списков
JM
какая модель?
?
CD
Очевидно, что чем более равномерен подсчет представителей каждого множества, тем больше существует способов выбрать k разных. Это очень сильно наталкивает на мысль, что попытки синтезировать числа по одному способомами выше приведут к неравномерному ответу
JM
А если сгенерировать k элементов в случайных местах, а потом заполнить остальные?
JM
Окей, нужен алгоритм, который может сгенерировать любой из удовлетворяющих условию списков
Ладно, с разными вероятностями проще
CD
Способов выбрать k мест таких, что все числа различны, все еще не одинаково
A
ну... можно сначала взять случайную перестановку из n чисел от 1 до n. Потом для каждого: если число больше k, то выбрать случайное из всех. Иначе выбрать случайное из конкретного множества
A
но это то же самое, что было предложено изначально, просто перемешивание выдвинуто вперед
2020 June 28
N
Как найти медиану в массиве не сортируя его ?
EZ
Nikolay
Как найти медиану в массиве не сортируя его ?
Quickselect?
ПК
Nikolay
Как найти медиану в массиве не сортируя его ?
ну есть идея — бин. поиск за log n * n
ПК
но, мне кажется, это не то, что нужно
N
Quickselect?
А это как ? В чем суть алгоритма ?
ГЛ
Nikolay
Как найти медиану в массиве не сортируя его ?
Что такое не сортируя, есть алгоритм имитирующий быструю сортировку, каждый раз берём опорный элемент, смотрим сколько меньше него, сколько больше и решаем куда идти
EZ
Nikolay
А это как ? В чем суть алгоритма ?
Quicksort, но только на части где искомый элемент