Andrey
из ваших слов следует что мы можем выбрать нужное нам к а остальные отбросить и будет несложно? )
Andrey
что-то сомнительно мне…
Oleg
из ваших слов следует что мы можем выбрать нужное нам к а остальные отбросить и будет несложно? )
Да, если выбирать с правильным распределением
Oleg
Как велико k?
Andrey
а отбрасывать тоже хитро придется?
Andrey
к - как захочет юзер, от 1 до порядка миллионов
Andrey
но это я загнул немного, миллион ребер мало кто захочет, но алгоритм хорошо бы чтобы переварил
Alexander
@IIvana можно и как ты решаешь
Oleg
Ну давайте простые случаи.
Представим, что k = 2 и у нас равномерное непрерывное на [0;1], тогда какова вероятность, что
большее из двух чисел не больше x?
Alexander
тебе нужно расставить номера из [1..N] для M позиций
Oleg
Oleg
P(max(a, b) < x) = P( a < x && b < x) =
P(a < x) * P(b < x) = x^2
Andrey
у нас 3 варианта - 2 слева, 2 справа и по одному там и там. по Гауссу хотел бы рассчитать вероятности этих событий и кинуть монетку
Oleg
Отмасштабировав правильно такое распределение на целые числа легко выбрать сначала максимум, а потом второе число от нуля до первого
Oleg
Теперь представим, что k - нечётное?
Andrey
а какая разница?
Oleg
Тогда мат-ожидание середины равномерно
Andrey
не вижу чем это поможет. нам не матожидание нужно а генерировать испытания каждый раз с неравномерным исходом
Oleg
Выбираем середину, потом выбираем рекурсивно k/2 чисел справа, k/ 2 слева
Andrey
и получаем равномерную сетку - ок )
Andrey
ее я могу и проще через шаг получить )
Oleg
не вижу чем это поможет. нам не матожидание нужно а генерировать испытания каждый раз с неравномерным исходом
Не понял, какой случай вам не понятен.
Andrey
нечетность к чем так выделяется?
Oleg
Andrey
кинуть монетку и выбрать - что выпадет
Oleg
И делать специальный мэппинг с пропусками
Oleg
Если k - очень большое
Alexander
ещё есть странный вариант, просто вызывать random shuffle на вершинах
Oleg
К с правильным алгоритмом можно помнить только логарифм и никаких пропусков учитывать не нужно
Andrey
при любом к не придется ничего запоминать - алгоритм волшебен, только Гаусса прикрутить
Andrey
шаффл интересная идея...
Alexander
не знаю, думаю пока что
Алексей
Придумал отличный рекурсивный алгоритм. Нам надо придумать набор N рёбер из K возможных. Они у нас как-то занумерованы и задача сводится к генерации битвектора дл ины K с N единицами
У нас равнораспределение, потому первый элемент 1 с вероятностью K/N.
1. Выбираем его случайно
2. Если он 1 задача сводится к (K-1,N-1), иначе (K,N-1)
Алексей
Нужно сгенерировать N случайных чисел, где N —число рёбер
Andrey
щас скопипасчу пока не уехало и почитаю вдумчиво…
Алексей
А алгоритм @IIvana я так и не понял
Oleg
Как выбрать миллион гарантированно разных целых чисел в диапазоне от 0 до C(5000,2500), не запоминая ничего на каждом шаге
Alexander
ну с этого начинается все
Алексей
:(
Евгений
Увидел "если будет много офытопа -- отправлю в блах" и 150 непрочитанных сообщений
Alexander
ну или запоминая минимум
Alexander
тут почти спец олимпиадка!
Alexander
я так понял идея такая - разбиваем отрезок на 2, выбираем сколько элементов попало в первую половину
Alexander
рекурсивно продолжаем
Alexander
тогда нам нужно помнить log(N*M/2) чисел (сколько точек в соотв отрезке)
Oleg
А. Я неправильно понял алгоритм
Alexander
ну или побить на большее число отрезков, тогда вообще помнить 1 число придётся
Oleg
Тогда да - ок
Alexander
я так понял решение @IIvana
Alexander
т.е. вопрос в том как эффективно выбирать это самое число только
Алексей
я так понял идея такая - разбиваем отрезок на 2, выбираем сколько элементов попало в первую половину
Так понял, но это как-то неэкономично. И считать надо всякие сложные вещи. В моем алгоритме надо понить два числа
Alexander
и держать битвектор
Alexander
я вроде это сначала предлагал
Alexander
правда по глупости предложил перебросить кубик если попали на выбранное
Alexander
но это не обязательно
Алексей
Битвектор материализовывать необязательно.
Alexander
ну список выбранных ответов помнить надо?
Alexander
или фунцию преобразования
Alexander
а как тогда?
Andrey
у меня ничего помнить не надо! у меня патологическая рекурсивная сортировка сама все помнит на стеке
Alexander
стек == помнить
Алексей
Можно сразу употреблять. Но есть граф сильно разряженный, то алгоритм будет неэкномичный. Он O(число возможных ребёр)
Alexander
я правильно понял твое решение, кстати?
Andrey
посчитай глубину стека для числа ребер 1000000 - мизер ) да, решение понял правильно
Andrey
вся соль - разбить число не пополам а отрезок пополам
Alexander
а понял
Alexander
все мой комментарий снят
Алексей
ну список выбранных ответов помнить надо?
Есть есть хорошее упорядочивание, то необязательно
Alexander
проходим по всем и выбираем его с вероятностью k/n
Алексей
k/n меняется с каждым шагом
Alexander
потом меняем вероятность в зависимости от результата
Alexander
угу
Oleg
а как тогда?
Биномиальным распределением понимаешь, сколько элементов должно идти в левый подотрезок
Спускаешься рекурсивно то в него, потом во второй с оставшимися. Пока размер отрезка не станет сравнис с количеством точек в нём и можно будет опять запустить выбор C
Andrey
а вот это я уже не понимаю (
Alexander