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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Да, задача не имеет вообще ничего общего с тем, что вы написали вначале. Надо найти число подотрезков - то есть, фрагментов последовательности без пропусков. Ограничения "нельзя удлинять отрезок, если сумма достигла M+1" у них нет - они говорят только, что можно и не удлинять. То, что "воспользуемся модулем", не означает, что надо брать сумму модулей - иначе ответ был бы около 50. Вероятно, имеется в виду, что модуль суммы должен быть больше M (из примера этого понять нельзя, в нём нет отрезка с суммой меньше -8).
    Могу сказать, что задача совсем непростая. Грубой силой она не решается (требуется N^2/2 сравнений, в секунду не уложитесь).
    Я бы делал так. Взять массив частичных сумм (0, a0, a0+a1, ...). Потом сделать log_2(N) копий этого массива (занумерованных индексом k от 1 до log_2(N)), и в каждом из них отсортировать отрезки длиной 2^k. Для массива из задачи это будет выглядеть так:
    S0=S[0]=[0,-2,7,10,16,19,27,26,36,30,37]
    S[1]=[-2,0, 7,10, 16,19, 26,27, 30,36, 37]
    S[2]=[-2,0,7,10, 16,19,26,27, 30,36,37]
    S[3]=[-2,0,7,10,16,19,26,27, 30,36,37]
    К сожалению, массивы S[1],S[2],S[3] оказались одинаковыми - это потому, что в примере мало отрицательных чисел.
    Имея такие массивы, вы легко ответите на вопрос "сколько чисел в фрагменте массива S0[k+1]..S0[N] не принадлежат диапазону S0[k]-M .. S0[k]+M" (время - log(M)^2). Сумма таких ответов для всех k от 0 до M-1 и даст ответ на задачу. Полное время - M*log(M)^2.
    UPD. Лучше бы они писали условие по-английски. Было бы не так стыдно за формулировку.
    Ответ написан
  • Где применяется комбинаторика в информатике?

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

    UPD. Можно вспомнить одно место, где комбинаторика требуется в обычных задачах. Это когда у нас есть множество каких-нибудь подмножеств, перестановок, слов над алфавитом, или ещё чего-нибудь, что обычно считает комбинаторика. И мы хотим по элементу этого множества найти его индекс. И наоборот.
    Задача возникает не часто, но если возникла, то без комбинаторных формул не обойтись никак.
    Ответ написан
  • Как построить сложный алгоритм на комбинаторику?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    static int sstep;
           static void FindAll(int N,int sum,int step,bool ord){
                sstep=step;
                sum/=step;
                fill(new int[N],N,sum,sum-N+1,ord);
            }
            static void output(int[] A){
                  Console.Write("{0}",A[0]*sstep);
                  for(int i=1;i<A.Length;i++) Console.Write("/{0}",A[i]*sstep);
                  Console.WriteLine();
            }
    
            static void fill(int[] A,int N,int sum,int smax,bool ord) {
                if(N==0 && sum==0) {
                    output(A);
                    return;
                }
                if(N==0 || sum<N) return;
                int smin=ord ? 1 : (sum-1)/N+1;
                N--;
                for(A[N]=smin;A[N]<=smax;A[N]++) {
                    fill(A,N,sum-A[N],ord ? sum-N+1 : A[N],ord);
                }
            }

    Задаётся A=new int[N], и вызывается fill(A,N,sum,sum-N+1,ord), где N=6, sum=300, ord - true, если с учётом порядка и false, если без учёта. Я проверял для N=5, sum=10 - там число вариантов приемлемо. Насколько я понимаю, для (6,300,true) будет примерно 21 миллиард комбинаций (Comb(299,5)), а для (6,300,false) - не меньше 30 миллионов.
    Ответ написан
  • Как распределить грузы по вагонам равномерно?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    (Про исходную задачу)
    После того, как отправили самые тяжелые грузы (которые больше средней загрузки вагона), пересчитываем среднее арифметическое, и начинаем укладывать грузы в вагоны, начиная с самого тяжелого. Возможны три стратегии.
    1) Очередной (самый тяжелый из оставшихся) груз кладём в самый пустой вагон
    2) Очередной груз кладём в самый загруженный из вагонов, в которые этот груз ещё помещается (т.е. общий вес вагона и груза не превосходит среднего арифметического)
    3) Очередной груз кладём в случайный из вагонов, в которые груз помещается.
    В стратегиях (2,3) иногда будет возникать ситуация "груз положить некуда". Тогда кладём его в самый пустой вагон, и отправляем.
    Дальше надо экспериментировать, чтобы выбрать более подходящую из этих стратегий. Интуиция тут не очень помогает.

    Если у вагона есть предел загрузки L, то груз, который не умещается даже в самый пустой вагон, оставляем до следующего поезда. При его загрузке сначала раскидываем очень тяжелые грузы, потом - оставленные от предыдущего поезда, потом - все новые.
    Ответ написан
  • Как найти все комбинации символов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Такие матрицы, судя по всему, описывают возможные бинарные операции на множестве {'a','b','c'}, т.е. функции от двух переменных из этого множества, принимающие значения в этом же множестве.
    Всего таких функций будет 3^9=19683. Поэтому достаточно перебрать числа от 0 до 3^9-1, и троичную запись каждого из них превратить в матрицу. На C# это бы выглядело так:
    char[,] matr=new char[3,3];
        for(int i=0;i<19683;i++){
            int a=i;
            for(int j=9;--j>=0;){
                matr[j/3,j%3]=(char)('a'+a%3);
                a/=3;
            }
            Process(matr);
        }
    Ответ написан
  • Сколько существует различных уникальных подпоследовательностей из последовательности цифр длиной N?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Хорошая задачка, жаль, что я её раньше не заметил.
    Решение за O(N):
    static long nways(string seq) {
        long[] sum=new long[10];
        long cursum=1;
        foreach(char c in seq) {
            int d=c-'0';
            long x=cursum-sum[d];
            sum[d]=cursum;
            cursum+=x;
        }
        return cursum-1;
    }
    Ответ написан
  • Поиск наиболее подходящих наборов из последовательности (очень много сочетаний)

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Есть пример для L=22:
    0011 1111 1111 1100 0000 00
    0000 0000 1111 1111 1111 00
    0101 0101 0101 0101 0101 01
    1010 1010 1010 1010 1010 10

    Здесь «жадный» алгоритм выдаст пару (1,2) — 18 единиц, и уйти из нее уже не удастся, остальные пары кроме (3,4) дают только 17. Так что моя эвристика тоже не работает.
    Ответ написан