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

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас ошибка: надо еще P30(0) прибавлять.

    Какой-то более простой формулы мне придумать не удалось, и она вряд ли есть. Если руками вывести формулы для маленького количества банков, то там все-равно получается полином n/2-ой степени, т.е. от 15 слагаемых никуда не уйти.

    Я думаю, в этой задаче у вас приняли бы просто символьную записть в виде суммы.

    Если нужно числа - можно написать программу, или считать на калькуляторе. Начинайте с 0.7^30. Делайте m+, домножайте на 3/7*30/1, потом на 3/7*29/2, и так далее (нажимая m+ каждый раз), пока 15 слагаемых всего не наберется.

    Или вбить в wolframalpha и получть 98.3%.
    Ответ написан
  • Алгоритм для минимизации стоимости товаров от разных поставщиков, какие ресурсы изучить?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Можно свести к линейному целочисленному программированию (linear integer programming).

    Индикаторные переменные (0 или 1) - покупаете ли вы этот товар у этого продавца (x_ij).
    Еще переменные - платите ли этому продавцу за доставку (y_j).

    Ограничения:

    y_j >= x_ij
    sum_j (x_ij) = 1

    Целевая функция - мнинимизировать затраты: sum_ij x_ij*c_ij + sum_j y_j*d_j

    Потом решать каким-либо солвером (есть куча быстрых библиотек).

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

    Можно еще полный перебор с отсечениями. Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару. Это значит, что можно поддерживать текущие минимальные цены на все товары у выбранных продавцов (+бесконечность, если никто не продает этот товар). Вы можете брать какого-то продавца, только если его цена по какому-то товару меньше. Ну и всякие ранние выходы - если сумма минимальных цен вообще по всем + текущие траты за доставку выше оптимального пока что ответа, дальше добавлять продавцов смысла нет.
    Ответ написан
  • Как перебрать все возможные комбинации символов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Готовой функции нет.

    Нужно или писать рекурсивную функцию, или итеративно дописывать ко всем элементам массива по одному элементу из сделеющего множества. Просто переведите этот код на с++.

    Рекурсивная функция вроде как должна быть более дружественная к аллокациям и по этому - быстрее.
    Ответ написан
  • Как найти количество перестановок числа?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это комбинаторика.

    Если бы не было ограничения на то, что первый символ не 0, то было бы гораздо проще. Частый прием в комбинаторике - подсчитать количество всех возможных вариантов, а потом вычесть количество "плохих" вариантов. Временно разрешим нулю быть первой цифрой, решим задачу. Потом зафиксируем ноль на первой позиции и подсчитаем сколько таких вариантов и вычтем их. Для этого можно вычеркнуть один ноль из числа, решить ту же самую задачу.

    Еще, в вашей формуле направшивается добавить пустое число ("") в ответ. Давайте разрешим его и вычтем в конце 1.

    Еще, очевидно, результат зависит только от количества каждой цифры в исходном числе, но не от их порядка.

    Поэтому пусть f(a0,a1,...a9) - сколько есть способов расставить некторые из a0 нулей, a1 единиц, a2 двоек, и т.д. (ноль может идти в начале, число может быть пустым).

    Ответ к задаче f(a0,a1,...a9)-1-min(a0,1)*f(a0-1,a1,...a9). Последнее слагаемое считает варианты, начинающиеся с нуля. Оно не вычитается, если нулей в числе нет. -1 посередине вычитает пустое число из ответа (но ее нет в последнем слагаемом, ведь мы там еще 0 в начале приписываем и пустое число надо считать).

    Теперь самое интересное, формула для f(a0,a1,...a9). Замкнутой формулы я не нашел, но придумал, как считать алгоритмом.

    Можно все варинаты разделить по количеству символов в числе (n), от 0 до суммы a0...a9. Давайте подумаем, где могуть быть девятки? i <= a9 из них попадут в ответ. Они могут быть на C(n, i) позициях. Останется разместить остальные цифры на n-i позиций.

    Вырисовывается следующее динамическое программирование:

    F(i, n) - сколько способов разместить первые i цифр на n позициях (возможно, беря не все цифры).

    F(i,n) = sum (j=0..min(a[i-1], n)) F(i-1, n-j)*C(n, j)
    F(0, n>0) = 0
    F(i,0) = 1.
    Ответ - sum(k=0..a0+...+a9) F(9, k)

    У функции как бы неявный параметр массив a[] количеств всех цифр, но я его не включаю в параметры динамики, потому что по нему не надо мемоизировать.

    Не забудьте, что для подсчета второй динамики, для f(a0-1,...a9) надо будет полностью отчистить мемеоизацию, потому что массив a поменялся же.

    Этот алгоритм работает за O(9*n), где n - длина входного числа.

    Вот пример для входного числа 112: все цифры, которых в числе нет можно выкинуть из рассмотрения и работать с массивом a={2,1} (для всех десяти цифр слишком много писать).

    F(0,0) = 1
    F(0,1) = 0
    F(0,2) = 0
    F(0,3) = 0
    F(1, 0) = 1
    F(1,1) = F(0, 1)*C(1,0) + F(0,0)*C(1,1) = 1
    F(1,2) = F(0,2)*C(2, 0)+ F(0,1)*C(2,1) + F(0,0)*C(2,2) = 1
    F(1,3) = F(0,3)*C(3, 0)+ F(0,2)*C(3,1) + F(0,1)*C(3,2) = 0
    F(2,0) = 1
    F(2,1) = F(1,1)*C(1, 0) + F(1,0)*C(1,1) = 2
    F(2,2) = F(1,2)*C(2, 0) + F(1,1)*C(2,1) = 3
    F(2,3) = F(1,3)*C(3, 0) + F(1,2)*C(3,1) = 3

    Ответ F(2,3)+F(2,2)+F(2,1)+F(2,0) = 3+3+2+1= 9.

    Вычитаем 1 (пустое число) и получаем 8 чисел, как у вас в примере для 112.
    Ответ написан
  • Как решить эту комбинаторную задачу?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Представьте вашу строку, и нарисуйте палочки между двумя соседними битами там, где проходит граница блоков. Вопрос в задаче подсчитать количество способов расставить эти палочки правильно (стоит обязательно палочка в самом начале и самом конце, между любыми соседними палочками - ровно одна единица).

    Из условия получается, что между двумя единицами, разделенными некоторым (может и пустым) количеством нулей, обязательно должна стоять ровно одна палка. Т.е. границы расстановки разных палок не пересекаются. есть одна между первой и второй единицей. одна между второй и третьей и т.д.

    Вот и считайте, сколько вариантов поставить палку перед каждой единицей. Надо подсчитать расстояния между каждой парой единиц и перемножить. Если единиц вообще нет - ответ 0, если одна - то 1.

    Можно сделать за один проход, если запоминать, где стояла предыдущая единица.

    int64_t CountWaysToSplit(std::string s) {
      int last_one = -1;
      int64_t res = 1;
      for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '1') {
          if (last_one >= 0) res *= i - last_one;
          last_one = i;
        }
      }
      return last_one >= 0 ? res : 0;
    }
    Ответ написан
  • Как составить все возможные сочетания из элементов разных массивов размером N?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Во первых, загоните входные данные в двумерный массив, или список массивов или что там вообще в php есть, чтобы можно было взять первый, второй и т.д. входной массив по номеру или перейти к следующему.

    Далее, как вы уже знаете, нужна рекурсивная функция. Передаевайте ей уже собранную часть ответа и какой из массивов надо использовать следующим (итератор в списке или номер в массиве).

    Функция берет из текущего массива один из элементов в цикле и добавляет его к ответу и запускается рукурсивно от следующего массива. Еще функция не берет ничего из текущего массива и запускается рекурсивно.

    Надо вставить следующие проверки: Если функция запущена от после-последнего массива, то надо вывести текущий ответ. Цикл по элементам текущего массива пропускается, если в ответе уже максимально возможное количество элементов.
    Рекурсивный вызов без добавления элемента пропускается, если оставшихся дальше массивов столько же, сколько не хватает элементов в текущем ответе до минимально нужного размера.

    Псевдокод примерно такой (не php, чтобы не позориться):

    function Generate(result, array_index, arrays) {
      if(result >= len(arrays)) {
        print(result)
        return
      }
      if (min_length - len(result) < len(arrays)-array_index-1) {
        Generate(answer, array_index+1, arrays);
      }
      if (len(answer) < max_length) {
        for i = 0...len(arrays[array_index]) {
          answer.push_back(arrays[array_index][i]);
          Generate(answer, array_index+1, arrays);
          answer.pop_back();
        }
      }
    }
    Ответ написан
  • Количество комбинаций чисел JavaScript?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    В тупую можно подсчитать 2-мя вложенными циклами.

    ans = 0;
    for (i = 1; i <= 3; ++i) {
      for (j = 1; j <= 3; ++j) {
        mn = max(n - i - j - 3, 1);
        mx = n - i - j - 1;
        if (mn <= mx)
          ans += mx - mn + 1;
      }
    }


    Работает так - перебираем сколько символов в первом и втором блоке. После этого считаем, сколько минимально и максимально может быть символов в третьем блоке (оставляя на последний от 1 до 3 символов). Прибавляем к ответу количество возможных вариантов для длины третьего блока.

    Но это если у вас параметры фиксированные (4 блока 1-3 символа). Если параметры могут меняться, то решение - динамическое программирование f(i,k) - сколько способов разбить первые i символов на k блоков.

    База: f(0,0) = 1, f(0, k>0) = 0, f (i>0, 0) = 0;
    Пересчет: f(i,k) = sum_{l=min_length...min(max_length, i)}(f(i-l,k-1)).
    Ответ: f(n, num_blocks).
    Ответ написан
  • Комбинаторика в Java Script, как добавить точку во всех возможных комбинациях массива?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Делайте рекурсивную функцию, которая решает вашу задачу. Если символ на входе 1 - просто его и возвращает. Если входных символов несколько - то откусывает последний символ и вызывается рекурсивно, потом к возвращенному массиву к каждому элементу дописывает последний символ и точку-последний символ (новый массив с удвоенным количеством элементов).

    Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].
    Ответ написан
  • Карты, колода 36 карт 1 туз и одна черви?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если у вас задача - что в выбраных наугад картах есть хотя бы один туз и хотя бы одна черва, то надо найти Count(>0 червей И >0 тузов). Можно это инвертировать, считая все плохие варианты, вычев их из всех вариантов:

    Count(>0 червей И >0 тузов) = Count() - Count(0 червей ИЛИ 0 тузов)

    Дальше, COUNT(A или B) можно разложить на Count(A) + Count(B) - count(A И B).

    Финальная формула для ответа:

    Count() - Count(0 червей) - Count(0 тузов) + Count(0 червей И 0 тузов)

    Фактически, это форомула включения-исключения. Но в итоговой формеле все просто счиатать:

    Count() = C(5,36) - все варинты: сочетания по 5 из 36.

    Count(0 тузов) = С(5, 32) - нельзя брать тузы

    Count(0 червей) = С(5, 27) - нельзя брать 9 червей

    Count(0 червей И 0 тузов) = С(5, 24) - нельзя брать 9 червей и 3 оставшихся туза.

    Подсчитайте через фаториалы и сложите с правильными знаками.

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

    В первом случае оставшиеся 4 карты - любые из 24 карт не-тузов-не-черв, т.е. эта часть - C(4,24). Во втором случае, вы берете какой-то из 3 тузов, какой-то из 8 черв и оставльные 3 карты из не-тузов-не-червей, т.е. ответ 3*8*C(3,24). Обе части просуммируйте.
    Ответ написан
  • Как выполнить свертку сочетаний?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Странно задача сформулирована, но, кажется, надо просто найти все уникальные числа во входных данных.
    Или какой-нибудь set используйте, или сложите все входные числа в массив, отсортируйте и потом удалите повторяющиеся подряд идущие элементы.
    Ответ написан
  • Как реализовать алгоритм комбинаторики в программе?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Сначала переведите картинку из залачи в числа. Вот есть у вас 20 точек, пронумерованные от 1 до 20, как-то. Выпишите все 12 групп (9 окружностей и 3 диаметра). Будет у вас 12 наборов по 5-6 номеров. Запишите их в программе константными массивами.

    Затем делайте перебор рекурсией: У вас в глобальном массиве или списком в параметре будет набор пока не поставленных чисел. Сначала проверьте, что вы не сделали уже 2 группы с разной суммой. Пройдитесь по всем 9+3 группам, если какая-то целиком уже заполнена, то записываете ее сумму в переменную для окружности или диаметра, соответственно. Если перед записью там уже была другая сумма -то вы нашили противоречие. В этом случае надо просто вернуться из текущей рекурсии назад.

    Если противоречий нет и вы все 20 чисел поставили - выводите ответ.

    Иначе - перебираете, какое число ставите в первую незаполненую точку циклом. Ставите туда число и вызываетесь рекурсивно.

    Надо только аккуратно уже поставленные на картинке числа в нужные места поставить. Для этого их, во первых, не включйте в список непоставленных чисел, во вторых на заполенные позиции ставьте уже записанное там число.

    Просто перебирать все перестановки (наборы массивов из чисел без повторений) и в конце проверять суммы, как вы хотите сделать - будет слишком долго. Их 21! (факториал) - это дофига слишком.
    Ответ написан
  • Как реализовать алгорим задачи о сумме подмножеств?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Обычная динамическое программирование работает для повторяющихся чисел, тут не должно быть проблем. Отрицательные числа решаются просто - считаете все возможные суммы только положительных чисел стандартной динамикой и отдельно только для отрицательных чисел (опустив знак). Потом одним циклом перебираете сумму положительных чисел x>=S и смотрите, если x-S можно набрать отрицательными числами. На общую сложность этот цикл не влияет.
    Ответ написан
  • Какой размер доминирующего множества направленного графа (турнира)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Доказательство по индукции. Для одной или двух вершин всегда будет 1 в D.

    Пусть degree(v) - количество вершин, инцидентных v.
    Лемма: В турнире с n вершинами будет хотя бы одна с degree() >= (n-1)/2. Иначе, просуммируем все degree().
    С одной стороны, сумма будет равна количеству ребер, т.е. n(n-1)/2. С другой, эта сумма < n*(n-1)/2 по предполоджению. Противоречие, значит существует v: degree(v) >= (n-1)/2

    Теперь докажем основное утверждение.
    Рассмотрим турнир с n>2 вершинами. Там есть хотя бы одна v: degree(v) >= (n-1)/2. Включим ее в D. и удалим из графа ее и все, которым она инцедентна. Мы удалили из графа не меньше 1+(n-1)/2 вершин, фактически уполовинив количество вершин в графе. По индукционному предположению там надо log(n/2) вершин в доминирующем множестве. Иы добавили к ней 1. Поэтому в итоге нам надо log(n) вершин и для этого графа.

    Это же доказательство можно использовать для построения D - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.
    Ответ написан
  • Как найти минимальное время которое удовлетворяет условие?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это перефразированная задача о рюкзаке. Надо только заметить, что в оптимальном ответе будет набрано менее K+100 очков. Иначе можно безболезненно выкинуть какую-нибудь миссию (а они все <100 секунд занимают).

    Решение динамическим программированием. Не буду тут повторять - оно простое и везде расписано. Еще раз напомню ключевые слова - "задача о рюкзаке".
    Теперь цена предмета в задаче о рюкзаке - это время, а вес предмета - это очки. Заполняем DP[i] - минимальное время за которое можно набрать i очков. Потом ищем минимум на отрезке [k..k+100). Это и есть ответ к задаче.
    Ответ написан
  • Какой алгоритм использовать для определения минимального числа перестановок карт в колоде?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Правильный ответ - 52-<длина наибольшей общей подпоследовательности>.
    Выводится он так:
    1) Ни одну карту нет смысла двигать 2 раза. Т.е. ответ 52-<количество неподвижных карт>
    2) Неподвижные карты находятся в том же порядке в обеих колодах, следовательно они образуют наибольшую общую подпоследовательность.

    Наибольшая общая подпоследовательность - вообще-то это их обработки строчек тема, будем считать что у нас даны 2 52-символьные строки, один символ-одна карта, все символы разные. НОП - это такая наибольшая строка, которая останется, если выкинуть из первой и второй строки какие-то символы. Ищется она за квадратичную сложность (в данном случае - моментально, строчки-то фиксированной длины) динамическим программированием.

    F(i, j) - длина наибольшей общей подстроки у префиксов длины i у первой строки и длины j у второй.

    База F(0,*)=F(*,0)=0

    Переход: F(i,j) = max(F(i-1,j), F(i,j-1), F(i-1,j-1)+1). Третий вариант рассматривается только, если i-ый символ в первой строке и j-ый во второй равны.

    Ответ - 52-F(52,52) для вашей задачи

    Если надо выдать куда что перемещать, то задача чуть сложнее. Динамика модифицируется сохранением, какой из трех вариантов был выбран, чтобы потом восстановить НОП. Эти карты помечаются как неподвижные. Потом, для всех карт во второй колоде найдите их места в первой колоде. А потом, тупо, перемещайте подвижные карты по одной на нужные места в возрастающем порядке результирующих мест. Тогда не надо будет вообще учитывать пока не перемещенные карты.
    Ответ написан