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

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

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

Я опять не понял задачи? Я так понял, что мы должны сгенерировать 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

выбрали, четверного 7/7=1

и т.д.

фигасе. круто. признаЮ поражение своего велосипеда с половинным делением…

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

но я боюсь что там большая арифметика и в js это может быть печально (или нет?)

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

кстати про половинное деление - эффективнее делить на L отрезков

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

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

в этом случае у тебя не будет расти стек

а будет просто цикл по отрезкам

на L можно, но там гаусса сложнее еще считать

на самом деле это у тебя получится решение похожее на решение Алексея, но более крупными блоками

там при сравнительно небольших N уже будут отклонения Гаусса от честного биномиального играть

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

у меня есть подозрение, что там можно как-то всё упростить

но проще решение какое понимаешь и точно работает

а дальше уже смотреть, нужно ли что-то ещё делать

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

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

вместо хранения дерева на пару Гб обошлись тройкой 128 битных чисел

выгода!

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

обязательно по порядку

иначе придется ещё стейт хранить

что кстати плюс т.к. юзеру ты их упорядоченно выдавать будешь

так и думал, просто уточнил ) ващекласс алгоритм!

можно прям стримить

и могу еще и лениво )

прямо строить граф по порядку поступающих ребер

можешь ещё сразу анализ на стриминговых алгоритмах считать

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

как stinger

ага, накопительные характеристики. все плюсы потокового генератора

http://www.stingergraph.com

timCF будет жить. Поприветствуем!

Привет. У меня нубский вопрос. Допустим есть две функции hello :: Maybe Int -> Int hello (Just foo) = foo world :: Int world = hello Nothing С точки зрения типизации тут всё правильно, но очевидно что 1) в функции hello не рассмотрены все возможные клаузы для типа Maybe Int 2) функция world из-за пункта 1 будет всегда бросать exception Как сделать так чтобы компилятор хаскеля указывал на подобные ошибки?

-Wall ключ компилятору передай

Эт не сложная. Стандартная по теорверу.

Я сложные даже придумать не смогу ) Есть N точек, равномерно распределенных на отрезке [0, 1]. Отрезок делится пополам. Каковы вероятности нахождения в левой половине отрезка 0, 1, .... N точек? Хочется получить аналитический вид кривой при стремлении N к бесконечности.

Привет. У меня нубский вопрос. Допустим есть две функции hello :: Maybe Int -> Int hello (Just foo) = foo world :: Int world = hello Nothing С точки зрения типизации тут всё правильно, но очевидно что 1) в функции hello не рассмотрены все возможные клаузы для типа Maybe Int 2) функция world из-за пункта 1 будет всегда бросать exception Как сделать так чтобы компилятор хаскеля указывал на подобные ошибки?

1) -Wincomplete-patterns 2) А это не ошибка

С -Werror станет ошибкой :)

В любом случае если нужна частичная функция (зачем?), то лучше это сделать явно через клоз с error

@DoctorRyner будет жить. Поприветствуем!

Хай, кто-нибудь юзал scotty?

Есть же servant