Перестановки в питоне, с изюминкой

Question

У меня есть список объектов (для примера, скажем, 5). Я хочу список некоторых возможных перестановок. В частности, учитывая, что некоторые пары не вместе, а некоторые тройки не делают бутерброды, как я могу генерировать все другие перестановки? Я понимаю, что сначала создаю их все и проверяю, работают ли они, но думаю, что было бы быстрее даже не учитывать пары и тройки, которые не работают.

Я ошибаюсь, что сначала будет быстрее проверить, а потом сгенерировать?

Как бы я это сделал?

Answer 1

Вам нужно будет найти алгоритм, который отключает более одной нежелательной перестановки после одной проверки, чтобы получить что-нибудь. Очевидная стратегия заключается в последовательном построении перестановок, например, в дереве. Затем каждый разрез удаляет целую ветвь.

редактирование:
Пример: в наборе (A B C D) предположим, что B и C, а также A и D не могут быть соседями.

       (A)                (B)                (C)                (D)
     /  |  \            /  |  \            /  |  \            /  |  \
 AB     AC    AD     BA    BC   BD      CA    CB   CD      DA    DB   DC
 |  \   |  \   X    / \    X    / \     / \   X    / \     X    / \    / \
ABC ABD ACB ACD   BAC BAD     BDA BDC  CAB CAD   CDA CDB     DBA DBC DCA DCB
 X   |   X   |     |   X       X   |    |   X     X   |       |   X   |   X
    ABDC   ACDB  BACD            BDCA  CABD         CDBA     DBAC    DCAB
     v       v     v               v     v            v        v       v

Каждая строка без скобок нуждается в проверке. Как вы видите, X (где поддеревья были обрезаны) сохраняют чеки, один, если они находятся в третьем ряду, и четыре, если они находятся во втором ряду. Мы сохранили здесь 24 из 60 проверок и опустились до 36. Однако в общем случае всего 24 перестановок в общем, поэтому, если проверка ограничений (в отличие от построения списков) является узким местом, было бы лучше просто построить все перестановки и проверить их в конце ... ЕСЛИ проверки не могут быть оптимизированы, когда мы пойдем этим путем.

Теперь, как вы видите, проверки нужно выполнять только для новой части каждого списка. Это делает чеки намного меньше; на самом деле, мы делим проверку, которая была бы необходима для полной перестановки, на маленькие куски. В приведенном выше примере нам нужно только посмотреть, может ли добавленная буква стоять вместо последней, а не все ли буквы раньше.

Однако, также, если мы сначала построим, а затем отфильтруем, проверки могут быть прерваны, как только встретится «нет». Таким образом, при проверке нет никакого реального выигрыша по сравнению с алгоритмом «сначала построим, а затем фильтруем»; скорее существует опасность дальнейших накладных расходов через большее количество вызовов функций.

Мы экономим время на создание списков и пиковое потребление памяти. Построение списка, как правило, довольно быстро, но пиковое потребление памяти может быть рассмотрено, если число объектов увеличивается. Для фильтра first-build-then-filter оба растут линейно с количеством объектов. Для древовидной версии она растет медленнее, в зависимости от ограничений. Из определенного количества объектов и правил также существует фактическое сохранение чека.

В общем, я думаю, что вам нужно попробовать это и рассчитать время двух алгоритмов. Если у вас действительно есть только 5 объектов, придерживайтесь простого (filter rules (build-permutations set)). Если количество ваших объектов становится большим, алгоритм дерева в какой-то момент будет работать заметно лучше (вы знаете, большой O).

Um. Извините, я попал в режим лекции; потерпи меня.