Задать вопрос

tumur4

Лайки

  • Как сгенерировать размещение по его номеру в лексикографическом порядке?

    hint000
    @hint000
    у админа три руки
    1. Организуем список из N элементов по возрастанию;
    2. Генерировать будем рекурсивно (это для простоты объяснения, после усвоения идеи можно обойтись циклом);
    2.1. Если M==0, то выход из рекурсии;
    2.2. Первый элемент размещения - это элемент, находящийся на L-ом месте в списке, где L=((N*m-1)\A(N,M))+1 (нумерация с единицы только для ясности); A(N,M)=число размещений из N по M; удаляем из списка выбранный элемент;
    2.3. Для следующего шага рекурсии берём m=m-(L-1)*A(N,M)/N; N=N-1; M=M-1;
    Ответ написан
    3 комментария
    3 комментария

  • Найдите перестановку по её номеру в лексикографическом порядке. Total - кол-во элементов, К - номер перестановки. Как сократить время программы?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Рассмотрим список всех перестановок в лексикографическом порядке. Этот список содержит N! перестановок. При этом его можно разбить по первому элементу на N непрерывных групп по (N-1)! перестановок.
    Таким образом, определить первый элемент перестановки с номером M (начиная с 0) можно как К1=⌊M/(N-1)!⌋ (также, начиная с 0). Внутри группы перестановка будет иметь номер M'=M mod (N-1)!.
    Вычеркнем найденный элемент из списка и повторим вычисления, пока не найдём все элементы.

    Пример:
    Элементы: (a, b, c, d).
    Перестановка M=11 (начиная с 0).
    Список (a, b, c, d). K1 = ⌊11/3!⌋ = 1. Элемент 'b'. M' = 10 mod 3! = 5.
    Список (a, c, d). K2 = ⌊5/2!⌋ = 2. Элемент 'd'. M' = 5 mod 2! = 1
    Список (a, c). K3 = ⌊1/1!⌋ = 1. Элемент 'c'. M' = 1 mod 1! = 0
    Список (a). K4 = ⌊0/0!⌋ = 1. Элемент 'a'.
    Получили перестановку (b, d, c, a).
    Сгенерируем все перестановки и проверим правильность:
    0: a, b, c, d
    1: a, b, d, c
    2: a, c, b, d
    3: a, c, d, b
    4: a, d, b, c
    5: a, d, c, b
    6: b, a, c, d
    7: b, a, d, c
    8: b, c, a, d
    9: b, c, d, a
    10: b, d, a, c
    11: b, d, c, a
    12: c, a, b, d
    13: c, a, d, b
    14: c, b, a, d
    15: c, b, d, a
    16: c, d, a, b
    17: c, d, b, a
    18: d, a, b, c
    19: d, a, c, b
    20: d, b, a, c
    21: d, b, c, a
    22: d, c, a, b
    21: d, c, b, a
    Ответ написан
    1 комментарий
    1 комментарий

  • Найдите перестановку по её номеру в лексикографическом порядке. Total - кол-во элементов, К - номер перестановки. Как сократить время программы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы генерируете перестановки по одной, пока не отсчитаете k. Это медленно, потому что k может быть очень большим. Перестановок-то n! - это дофига много.

    Надо генерировать ее сразу по номеру.

    Посмотрите на первый элемент. У первых (n-1)! перестановок там 1, у следующих (n-1)! - там 2, потом идет группа, начинающихся с 3 и т.д.

    Уже вы можете понять в какой группе искомая k-ая перестановка. Тупо floor(k/(n-1)!) (если нумерация с 0 и перестановок и групп). Фактически, формула для первого элемента - a[0] = (k-1)/(n-1)! + 1.

    Дальше вы можете выкинуть из рассмотрения первый элемент. Сфокусируйтесь на группе с заданным известным первым элементом. Какой номер искомая перестановка имеет среди этих (n-1)!? Надо из k вычесть количество перестановок c меньшими первыми элементами (их (a[0]-1)*(n-1)!. Потом задача сводится к преведущей - сгенерировать k-ую перестановку среди оставшихся n-1 элементов.

    Если использовать какое-нибудь дерево отрезков, чтобы быстро искать j-ый пока не занятый элемент, то все решение будет за O(n log n). Если делать совсем просто - двумя циклами - то будет O(n^2). Гораздо быстрее вашего O(n!).

    Надо только аккуратно обработать случаи, когда (n-1)! слишком большое. Фактически, вам надо найти максимальный факториал, который меньше k. Пока не спуститесь до этого момента нужно сразу брать первый незанятый элемент и не считать факториал вообще.
    Ответ написан
    Комментировать
    Комментировать