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

    jcmvbkbc
    @jcmvbkbc
    http://dilbert.com/strip/1998-08-24
    Смысл младших битов кода Грея зависит от значения старших битов, поэтому вряд ли можно избежать перевода значения из кода Грея в обычный двоичный. Если битность кода фиксированная и небольшая, скорее всего оптимальный вариант -- перевести в двоичный код и сравнить. Если битность большая или переменная, то можно переводить и одновременно сравнивать уже переведённые биты и останавливаться на первом неравенстве. См.
    Ответ написан
  • Какую формулу комбинаторики использовать?

    jcmvbkbc
    @jcmvbkbc
    http://dilbert.com/strip/1998-08-24
    Посчитать количество нулей и единиц в исходном числе. Пусть это будут N0 и N1.
    Если нули не могут стоять спереди, значит спереди может стоять только единица. Если N1 > 0, уменьшить N1 на 1, иначе нет решений.
    Теперь нужно упорядочить N0 нулей и N1 - 1 единицу всеми возможными способами. Их будет (N0 + N1 - 1)!. Но поскольку все нули и все единицы одинаковы, то разных комбинаций будет в N0! * (N1 - 1)! раз меньше, (N0 + N1 - 1)! / (N0! * (N1 - 1)!). Это -- перестановки с повторениями. Для числа 100101 результат 10:
    100011, 100101, 100110, 101001, 101010, 101100, 110001, 110010, 110100, 111000.
    Ответ написан
  • Как решить задачу (комбинаторика)?

    jcmvbkbc
    @jcmvbkbc
    http://dilbert.com/strip/1998-08-24
    Очевидно же, что они должны стоять М-Ж-М-Ж-М-Ж-М-Ж-М-Ж либо Ж-М-Ж-М-Ж-М-Ж-М-Ж-М.
    В каждом из вариантов видна независимая перестановка 5 мужчин и независимая перестановка 5 женщин. Всего получается (5! * 5!) * 2 = 28800
    Ответ написан
  • Какой алгоритм использовать для определения минимального числа перестановок карт в колоде?

    jcmvbkbc
    @jcmvbkbc
    http://dilbert.com/strip/1998-08-24
    Мои мысли на тему и получившийся алгоритм:
    - обозначим для простоты карты их порядковыми номерами в отсортированной колоде, Ai;
    - каждой карте сопоставим расстояние до её конечной желаемой позиции, равное i - Ai;
    - перестановка карты с позиции i на позицию j меняет её расстояние на j - i, и одновременно на sign(i - j) меняет расстояния карт между i и j;
    - перестановка выгодна если она уменьшает суммарное расстояние, которое потребуется пройти картам после неё;
    - для текущей позиции существует по меньшей мере одна наиболее выгодная перестановка -- такая, которая максимально уменьшает оставшееся расстояние; найти её можно тупым перебором исходной и конечной позиции переставляемой карты (но, может быть, можно и быстрее);
    - совершая на каждом шаге наиболее выгодную перестановку мы, скорее всего, упорядочим карты за минимальное число перестановок.

    Код на c:
    #include <limits.h>
    #include <stdio.h>
    #include <string.h>
    
    #define N (sizeof(a) / sizeof(a[0]))
    
    inline int sign(int d)
    {
            if (d == 0)
                    return 0;
            return d < 0 ? -1 : 1;
    }
    
    inline int abs(int v)
    {
            return v < 0 ? -v : v;
    }
    
    int main()
    {
            int a[] = {2, 1, 3, 4, 0};
            int q[N];
    
            for (;;) {
                    int best_profit = INT_MIN;
                    int best_src = -1;
                    int best_dst = -1;
                    int i, src, dst, tmp;
    
                    for (i = 0; i < N; ++i)
                            q[i] = i - a[i];
    
                    for (src = 0; src < N; ++src)
                            for (dst = 0; dst < N; ++dst) {
                                    int d = sign(dst - src);
                                    int profit = abs(q[src]) - abs(q[src] + dst - src);
    
                                    //printf("...%d -> %d: profit = %d", src, dst, profit);
    
                                    for (i = src + d; i != dst + d; i += d) {
                                            if (sign(q[i]) == d) {
                                                    ++profit;
                                                    //printf(" + 1");
                                            } else {
                                                    --profit;
                                                    //printf(" - 1");
                                            }
                                    }
                                    //printf(" = %d\n", profit);
                                    if (profit > best_profit) {
                                            best_src = src;
                                            best_dst = dst;
                                            best_profit = profit;
                                            //printf("... -- new best!\n");
                                    }
                            }
                    printf("%d -> %d (profit = %d)\n", best_src, best_dst, best_profit);
                    if (best_profit == 0)
                            break;
                    tmp = a[best_src];
                    if (best_dst < best_src)
                            memmove(a + best_dst + 1, a + best_dst, (best_src - best_dst) * sizeof(int));
                    else
                            memmove(a + best_src, a + best_src + 1, (best_dst - best_src) * sizeof(int));
                    a[best_dst] = tmp;
    
                    for (i = 0; i < N; ++i)
                            printf("%d ", a[i]);
                    printf("\n");
            }
            return 0;
    }
    Ответ написан
  • Как реализовать перебор случайных подмножеств?

    jcmvbkbc
    @jcmvbkbc
    http://dilbert.com/strip/1998-08-24
    Перебирать номера подмножеств по порядку, применять к номерам биективное преобразование (например блочный шифр) чтобы из порядкового номера подмножества получить его элементы.
    Ответ написан
  • Сколько существует различных уникальных подпоследовательностей из последовательности цифр длиной N?

    jcmvbkbc
    @jcmvbkbc
    http://dilbert.com/strip/1998-08-24
    Полный перебор можно существенно сократить не перебирая конкретные перестановки цифр: если выбраны цифры di, i = 1...m, среди которых есть группы одинаковых, с количеством цифр в каждой из этих групп cj, j = 1...k, то из этих цифр можно составить gif.download?%5Cfrac%7Bm%21%7D%7B%5Cprod разных чисел. Это число не зависит от конкретно выбранных цифр, только от размера групп одинаковых цифр, т.е. его значение можно посчитать раз и закешировать. Остаётся перебрать все выборки по m цифр из исходных n, их gif.download?%5Cfrac%7Bn%21%7D%7Bm%21%28, и для каждой из них, подсчитав размеры групп одинаковых цифр, определить, сколько можно составить разных чисел.
    Ответ написан