ладно, спасибо, пошел пробовать Карла Фридриховича и вспоминать как его получать из равномерного распределения

а аналитический вид у этого t наверное ужасный как и у биномиального? я могу пожертвовать точностью ради скорости расчета

Точка будет в пределе, но пока мы не перешли к пределу у нас будет бесконечное число делений. Можно просто выбрать какую-нибудь процедуру выбора деления

А что требуется считать?

Если интересно - расскажу откуда вылезла эта задачка

Конечно

Мне надо сгенерировать случайным образом граф с заданным числом вершин и ребер. Я свел ее к задаче получения заданного числа равномерно распределенных элементов из длинного вектора. Решал ее в лоб - для длинных векторов долго переводить в сеты уже набранные индексы чтобы потом их снова не выбирать. И придумал следующее - надо получить N равномерных индексов вектора. Я делю вектор пополам, и с какой-то рассчитанной вероятностью делю задачу на 2 подвектора - M в левой половине K в правой. когда N = 0 - я не беру никакую точку, когда 1 - беру равномерно из текущего интервала, когда N = число точек в интервале - беру все. Это граничные условия - а дальше простая рекурсия. В итоге мы тратим О(1) памяти и О(N) времени безо всяких огромных структур данным и мурыжения сетов с юнионами и вычитаниями. Дешево и сердито для больших графов, надо только M и K рассчитывать каждый раз вероятностным способом

Второй вопрос - из той же серии, только делим вектор не пополам а в рассчитанной вероятностно пропорции, а N делим пополам

а нельзя просто сгенерировать M пар из [1..N] и пересоздавать если такое уже было?

где M число ребер

поиск наличия ребра O(1)

можно, но если тебе надо сгенерировать 100499 ребер из 100500 то под конец долго ждать случайных попаданий

если памяти не жалко

можно разворачивать если больше половины генерировать отсутствующие ребра конечно

генерируй либо наличие, либо отсуствие ребер

смотря чего больше

но все равно это память, сеты и все такое. я уже думал над этим

битвектора ты хотел сказать?

мой же алгоритм выше - просто как тот ежик из анекдота - вжух!

мы похожую штуку делали

можно пронумеровать все выборки

ну битвектора, хэши или что там еще - неважно

и просто генерировать номер

с построить простой алгоритм перевода номера в сет

(ну у нас иерархическое дерево было, но там не важно)

я это и буду делать. только номера буду генерировать как выше написал

1 номер

давай на примере

кстати, вспомнил что у Гаусса то есть дисперсия…. ее надо как-то оценить по N получается…

A какое распредление у случайного графа? И как он представляется в памяти?

в моей модели - равномерно распределенная выборка N ребер из свего массива возможных

в памяти - неважно, как представлю так и будет

Ну то есть все графы, N вершим M ребёр

в смысле? V вершин, максимум V*(V-1)/2 ребер в неориентированном, берем из них N равномерно

смотри мы можем отметить ребро между вершиной 1 и остуствие 0, рассматриваем в одну сторону

чтобы дубли не считать

нам нужно выбрать M единичек в отрезке

мы можем все варианты упорядочить

например для 2 из 4:

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

[1100], [1010],[1001],[0110], ...

между этим представлением и его порядковым номером существует однозначное соотвествие

ты пронумеровал все графы?

выражаемое математической формулой, которую можно вывести за полчаса

поэтому тебе достаточно выбрать любое число от 0 до C_n^m

и увидеть что там не N единичек

чо?

да и само это число в инт не влезет, подозреваю

в инт64 у тебя все влезет

в а инт128 ещё и с запасом

в смысле? V вершин, максимум V*(V-1)/2 ребер в неориентированном, берем из них N равномерно

Число вершин фиксировано? Число рёбер фиксировано или случайно?

число вершин и ребер фиксировано

я так понял, что входные данные M, N - число ребет и графов

на выходе нужен граф

задается юзером - ему генерится граф

в а инт128 ещё и с запасом

Для небольших N,M

мои числа вершин не превзойдут 1000

какое С_n^M у нас не влезет в int128?

но это миллион возможных ребер

какое С_n^M у нас не влезет в int128?

C_132^66

Там факториалы, всёрастёт ОЧЕНЬ быстро

мои числа вершин не превзойдут 1000

Для таких нужно генерировать 996 случайных бит

http://m.wolframalpha.com/input/?i=log2%28C%281000%2C500%29%29

Ааа это, конечно же для 1000 возможных рёбер

)))

В худшем случае для 1000 вершин будет чото типа 5000 рёбер

http://m.wolframalpha.com/input/?i=log2%28C%285000%2C2500%29%29

Это 5000 бит

Ну вообще как видно C(n, n/2) растёт ненамного медленнее 2^n, так что можно считать n бит для комбинаций n/2 элементов из n

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

только аналитический вид формулы получить

Восстановление по порядковому номеру, как Александр посоветовал всё равно будет самым эффективным. Это я помню с каких-то кодфорсес задач

И выбрать k целых различных чисел в диапазоне без запоминания довольно простая задача

вот ее то я с таким трудом и решаю

надо обеспечить равномерность выборки, иначе взял К первых и все )

А сколько k?

Если k = 2^n - 1 совсем просто

а Матлаб остался на старом компе с Виндой, тут мак и нифига нет (…

Если другое - не совсем, но тоже несложно

К - любое заданное юзером