Блог пользователя konstantin.lex

Хитрая комбинаторика
Автор konstantin.lex, 12 лет назад, По-русски

Доброго времени суток, уважаемые программисты !

Вот сегодня столкнулся с задачей : есть n элементов (1,2,3,..,n) . Нужно научиться генерировать все перестановки из n элементов с заданным количеством инверсий за разумное время.
 Имеется в виду, что n>17, что делает полный перебор неприменимым .
Вот и суть вопроса - известны ли вам алгоритмы,которые помогут решить данную задачу ? Если есть какие-то мысли и не лень - выкладывайте, буду благодарен.


Пока есть мысль делать перебор с отсечением, если количество инверсий стало больше, чем задано . Но, наверное, это плохая идея . Что-то подсказывает, что можно применить динамическое программирование, но ума не приложу, как . 

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

Возможно я сильно туплю, поправьте.


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

UPD. Скорость работы зависит от допустимого числа инверсий. Как оптимизация - можно начинать с перестановки вида 54321. И да, наверное это то, что Вы подразумевали под "перебор с отсечением" и я торможу.
→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Если надо генерить все перестановки с данным числом инверсий - асимптотически это будет в любом случае почти факториал.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    Вернее Cf(k)n, что-то типа того

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -28 Проголосовать: не нравится
      Мне кажется, или вы действительно постоянно пытаетесь доказать, что ваше место не во 2-ом дивизионе/в *опе 1-го дивизиона, пытаясь "блеснуть" умом(частенько неудачно)??
      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится
        Почему во всём надо видеть попытку блеснуть умом? Вы как-то слишком негативно настроены.

        (Да заминусуют меня противники JKeeJ1e30)
        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вы просто предыдущих его комментов не читали:)... как только стал Майром, начал говорить, что теперь у него БОЛЕЕ МЕНЕЕ адекватное место в рейтинге. Как только стал рядовым начал опять ныть, что лучше прогать умеент
          (я кстати не минусовал=), лично против JKeeJ1e30 ничего не имею)
          → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Вы меня раскусили.


        Собственно, почему я думаю что это какая-то цешка или что-то типа того(конечно, я уже понял, что внизу не n):

        1 - один элемент (в любом случае ноль инверсий)
        1 1 - два элемента (либо одна инверсия, либо ноль)
        1 2 2 1 
        1 3 8 8 3 1.

        То есть мне кажется нужно искать аналогию с треугольником Паскаля.

        → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Может, поможет следующая идея. Пусть у нас есть какая-то перестановка, тогда в отдельной таблице t размером n в i-том элементе запишем, сколько инверсий в данной перестановке таких, что больший элемент в паре — i. Ясно, что для 1 это число 0, для 2 не больше 1, для 3 не больше 2 и т.д. Из такой таблицы можно и реконструировать данную перестановку — просто по очереди берём элементы от 1 до n и вставляем в создаваемую перестановку: i-тый элемент на ti элементов слева от последнего элемента.

Так вот, задача сведена к нахождению всех таких таблиц, где выполняется ограничение ti < i и сумма всех элементов — данное количество инверсий. Это уже выглядит полегче, и можно перебором разумным находить. Потом ещё всякие оптимизации добавлять. Но количество будет всё равно большим, как уже сказали.
→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

все перестановки, которые имеют одно количество инверсий не лежат в одной гиепрплоскости перестановочного многогранника. Тоисть они никогда не смежны.

Есть 2 алгоритма, решения этой проблемы (собственной разработки):
1) Базируеться на однозначном представлении инверсии перестановки в саму перестановку. Только тут один минус - сгенерировать все инверсии перестановок нужно используя перстановки возможных комбинаций. Под инверсией перестановки имею введу 0001 - для перстановки 1243.
2) Второй вариант сгенерировать 1 перестановку с количеством инверсий, которой равно К и пройти по всем смежным вершинам смежных вершин и взять через одну вершину, какраз эти вершины и будут иметь количество инверсий К.
Детали можешь узнать у меня (подойди на кафедру ПМИММ или ЕК)

→ Ответить