Ответы пользователя по тегу Алгоритмы
  • Сгенерировать M уникальных случайных чисел в диапазоне от 1..N. Быстрый алгоритм есть?

    @Sayonji
    Если вам не важно наличие строгой оценки, а важна скорость на практике, можете воспользоваться таким методом:
    1. Объявляете переменную p=M/N и списки L, R
    2. Делаете цикл i=1..N и добавляете число i в L с вероятностью p, иначе в R
    3. Теперь в L приблизительно M элементов, пусть d=M - |L|
    4. Если d>0, перебрасываете d случайных элементов из R в L, иначе наоборот из L в R
    Сложность получится O(N + dN), где d в среднем будет около sqrt(M(N^2-M^2)/2) / N

    Теоретическая оценка получается O(Nsqrt(M)), что хуже, чем случайное перемешивание списка 1..N за O(NlogN).
    Ответ написан
    Комментировать
  • Однородный итеративный семплинг в многомерном пространстве?

    @Sayonji
    Да точно так же можно, как и при делении на два.
    Предположим, аргументы нормированны, то есть от 0 до 1.
    Тогда по шагам:
    1) точка 0.5; 0.5; 0.5,…
    2) точки (0.25a), (0.25b), (0.25c),… | a,b,c = 1...3
    3) точки (0.125a), (0.125b), (0.125c),… | a,b,c = 1...7

    Ну, само собой, каждый раз берем те, которые еще не брали.

    Как получать точки для итерации?
    iters = new int[Nd] ;
    for (i = 1; ; i++) { // номер итерации
        step = 1 / 2^i; // полдлины интервала семплирования
        for ( /* iters пробегает все возможные наборы из чисел от 1 до (2^i - 1) */ ) {
            if ( /* все числа в iters четные */ )
                continue; // уже брали раньше
            sample F(iters[0] * step, iters[1] * step, iters[2] * step, ...)
        }
    }
    

    Ну и в строчке с sample надо повозиться с аргументами, чтобы сдвинуть их обратно в те диапазоны, где они были.

    Как добиться однородной плотности по всем аргументам. Если у них разные, но не слишком, диапазоны, нормировать их нужно самым большим из них. Т.е. сдвинуть все в [0; x], где x будет равно 1 только для самого длинного диапазона. А потом во втором форе (который будет работать как куча вложенных друг в друга) отсекать лишние хвосты. Т. е. если, например, 0.125 * iters[2] уже больше, чем величина х для третьего аргумента, то по этой переменной дальше не итерируем. Перед входом во второй for эти границы можно просчитать, это совсем несложно.
    И последнее. Если диапазоны отличаются значительно, то может иметь смысл как-то посчитать, с какой итерации следует начинать цикл, т.к. часть из них будет пропущена. Тем больше, чем больше различаются диапазоны.
    Как-то так, я думаю.
    Ответ написан
  • Решение задачио рюкзаке с использованием PuLP?

    @Sayonji
    Жаль, что я не знаю ни палп, ни питон, но всё-таки могу посоветовать кое-что попробовать.
    Ваша задача вроде бы и есть задача о рюкзаке практически.
    Проблема видна в бесконечном количестве переменных (в статье, на которую вы ссылаетесь, переменных всего три), но, скорее всего, библиотека позволяет что-то вроде такого:
    LpVariable cond = LpVariable(«cond», ...) // это будет цена набора
    LpVariable cond_num = LpVariable(«cond_num», ...) // это будет размер набора
    for each cocktail:
    .. tmp = LpVariable(cocktail.name, ...)
    .. cond = cond + tmp * cocktail.price // складываем цены
    .. cond_num = cond_num + tmp // складываем количества
    .. problem += tmp <= MAX, concat(«c», i) // каждый коктейль входит столько-то раз (или там <= cocktail.max, я не знаю)
    // я не знаю, как в питоне клеить строчки, i — это счетчик, пусть он начинается с 3, номера 1 и 2 зарезервируем

    Наверное, у cond должен быть какой-то другой тип, что-то типо Expression, надо документацию читать.

    Потом,
    problem += cond == CASH, «c1»
    problem += cond_num == CHECK_LEN, «c2»
    и, например,
    problem += 5, «obj»

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

    Я честно не знаю, имеет ли всё что я написал какой-то смысл (не разбираюсь, код копировал из статьи по ссылке), можете попробовать, если вариантов больше не будет. Надеюсь, как-то поможет.
    Ответ написан
    Комментировать
  • Книги по теории вероятностей и математической статистике

    @Sayonji
    Насколько не вводный?
    «Теория вероятностей» Боровкова
    «Проверка статистических гипотез» Лемана
    это вводные курсы?
    Ответ написан
    1 комментарий
  • Ищу алгоритм анализа нетривиальных данных

    @Sayonji
    А причем тут амплитуды? Я ведь верно понимаю, что амплитуды грубо говоря означают громкость? Тогда они практически не влияют на приятность ощущения. Скажем, можно взять обычный до-ми-соль, где до сильно отличается громкостью от ми, которая сильно отличается от соль. Получится вполне нормально звучащий аккорд, однако картинка совсем не будет похожа на первую в топике. А можно наоборот, взять до-до#-ре одинаковой интенсивности, тогда картинка будет ровной.
    В общем, кажется роль играют только частоты, интуитивно то же кажется. Ведь, раз там арфиметические прогрессии, всё должно быть достаточно периодично и пофигу на эту гиперболу.
    А насчет похожести на равномерность, мне ваша же идея кажется вполне подходящей.
    Постройте, говоря простым языком, «зависимость колва полосочек слева от частоты», получится набор точек. А его можно методом наименьших квадратов аппроксимировать прямой (а прямая это как раз равномерное распределение), там уже все дисперсии давно посчитаны.
    Ответ написан
    1 комментарий