не прямо выше а до этого -0 алгоритм Александра и Алексея

просто Алексея, я не решился предлагать этот алгоритм, хотя и думал о нём

смотри

берёшь первый элемент

какая вероятность того, что он в списке?

0

это конкретное ребро

в списке выбранных?

какая вероятность, что ребро (1,2) у тебя выбрано если всего у тебя N вершин, и из них выбрано K?

к/n

вот

бросаешь кубик, и узнаешь входит ли оно

или нет? )

верно

Спокой ночи

после этого у тебя 2 варианта

бросаешь кубик, и узнаешь входит ли оно

Тогда нужно запоминать выбранные графы

неа

Алексей - пасиб за биномиальное и Гаусса

у тебя 2 варианта: 1. выбрали, тогда решаешь задачу с (n-1) ребром и нужно выбрать (k-1) 2. не выбрали тогда n'=n-1, k'=k

и идешь по списку дальше

после этого у тебя 2 варианта

Тогда вероятность выбора ребра может отличаться от k/n

да, она изменяется после каждого выбора

но тогда я могу набросать кубик так, что к концу не наберу мое К

да, она изменяется после каждого выбора

Как её посчитать?

не можешь

или я туплю

Я сделал 1000 графов

если я правильно понимаю то или (k-1)/(n-1). или k/(n-1)

Как мне посчитать вероятность выбора первого ребра для 1001 графа?

она должна стать 1 при k=n

не понимаю вопроса

Если я знаю, что графы не должны совпадать

почему они должны не совпадать.. ничего не понимаю

Я опять не понял задачи? Я так понял, что мы должны сгенерировать k различных графов n вершин и m рёбер

не

одного графа хватит

пользователь говорит - сгенерируй мне граф из n вершин и m ребер

и ты генерируешь так, чтобы он был похож на случайный

ага

Блин, тогда один простой выбор числа от 1 до C(n*(n-1)/2 ,m)

хорошо бы, чтобы если пользователь ввел n и m ещё раз, то ему бы выдало другой граф

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

да должно быть

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

но это т.к. спать больше надо

т.к. я похожую задчу решал

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

Классическая нумерация комбинаций. Считаем их упорядоченными бит-векторами Как много элементов у которых первого элемента нет C(n-1, m) если выбранное число больше - вычитаем C(n-1, m) выбираем оставшиеся m-1 из n-1 Если нет - выбираем m из n -1с тем же номером

угу

единственное что мне не нравится что C(500*999,500) большое

единственное что мне не нравится что C(500*999,500) большое

C(500*999, 250*999) ещё больше

Но всё одно умножать и делить предвычисленные факториалы быстрее, чем генерить 250*999 рандомов

скорее всего

@IIvana достаточно запутали?

Можно сразу употреблять. Но есть граф сильно разряженный, то алгоритм будет неэкномичный. Он O(число возможных ребёр)

нет, О(число нужных ребер) - мы не лезем вглубь если чсло точек в интервале надо взять меньше 2

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

мой кстати нахаляву еще и сам граф строит при этом, не надо восстанавливать по огромному числу

мой кстати нахаляву еще и сам граф строит при этом, не надо восстанавливать по огромному числу

любой стоит граф, у нас же задача, вроде граф построить

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

даже на примере - возможных ребер 10, нам надо 8 - кинули 3 раза - не берем - все приплыли

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

А какой пакет вы используете для рандомных с заданным распределением?

какой пакет - у меня жс ))) сам писать буду из равномерного

погуглю как это делать, но вроде говорят можно

Тогда точно офтоп

даже на примере - возможных ребер 10, нам надо 8 - кинули 3 раза - не берем - все приплыли

Выбрали один раз рандомное от 1 до 45, потом построили граф с нужным индексом

не, Алексей другое писал, пойду вдумчиво перечитывать )

Если есть вершины а б в г и ребра аб и вг - это граф?

а какие сомнения? связность никто не обещал

если есть вершины а б в г и ребро аб - это тоже граф

хочет юзер граф с 4 вершинами и 1 ребром - юзер всегда прав

Тогда почему нельзя просто выбирать рандомные 2 точки из n записывая в хеш пока не наберется n ребер

вы наверное не читали все сообщения выше?

вы наверное не читали все сообщения выше?

Вежливо как

Вот думаю стоит ли

у такого подхода есть недостатки, скажем так

Очень интересно , проснусь почитаю

но до меня кажется начинает доходить как обойти мою загвоздку в алгоритме Алексея - если из 10 нам надо 8, мы подкинули 2 раза и оба мимо - тупо берем оставшиеся 8 и не подкидываем больше. тогда все быдет быстро и кучеряво, насчет равномерности только не уверен, хотя если небольшие отклонения то может и фиг с ней )

все ок там по вероятности

каждая следующая выборка хранит информацию (в двух числах) о том, сколько мы навыбирали

смотри вероятность первого 8/10, если не выбрали то вероятность второго 8/9, если не выбрали то вероятность третьего 8/8=1