Оптимизация уникальных необратимых перестановок в Python - PullRequest
Новая
       11

Оптимизация уникальных необратимых перестановок в Python

0 голосов
/ 12 апреля 2020

В настоящее время я пытаюсь решить задачу 'танцевальный концерт' kattis в Python 3. См. Здесь

После того, как я уловил количество выступлений Есть в танцевальном концерте, вы должны организовать выступления таким образом, чтобы последовательные выступления танцора были сведены к минимуму.

Я видел, как это задание выполнено в C ++, но мой код продолжал выполняться без времени, и я хотел оптимизировать его.

Вопрос: На данный момент, я генерирую все возможные перестановки производительности и запускаю сравнения из этого. Более быстрым способом было бы не генерировать все перестановки, поскольку некоторые из них просто перевернуты и привели бы к точно такому же выводу. 

import itertools
print(list(itertools.permutations(range(2)))) --> [(0,1),(1,0)] #They're the same, backwards and forwards
print(magic_algorithm(range(2))) --> [(0,1)] #This is what I want

Как я мог бы сгенерировать такой список перестановок?

Я пробовал:

-Произвести все перестановки, снова обработать их, перевернуть () дубликаты и сохранить их. Это занимает слишком много времени, и результат не может быть жестко закодирован в решение, поскольку файл становится слишком большим.

-Только генерирует перестановки до середины пути, затем останавливается, предполагая, что после этого нет уникальных перестановок генерируются (не так, как я выяснил)

-Я здесь проверял вопросы, но, похоже, ни у кого такой же вопрос, как у меня, то же самое в Интернете

Вот мой текущий код: 

from itertools import permutations

number_of_routines = int(input()) #first line is number of routines
dance_routine_list = [0]*10
permutation_list = list(permutations(range(number_of_routines))) #generate permutations

for q in range(number_of_routines):
    s = input()
    for c in s:
        v = ord(c) - 65
        dance_routine_list[q] |= (1 << v) #each routine ex.'ABC' is A-Z where each char represents a performer in the routine

def calculate():
    least_changes_possible = 1e9 #this will become smaller, as optimizations are found
    for j in permutation_list:
        tmp = 0
        for i in range(1,number_of_routines):
            tmp += (bin(dance_routine_list[j[i]] & dance_routine_list[j[i - 1]]).count('1')) #each 1 represents a performer who must complete sequential routines
        least_changes_possible = min(least_changes_possible, tmp)
    return least_changes_possible

print(calculate())

Редактировать: Принял душ и решил, что добавление справочной таблицы для сравнения двух элементов ускорит его, так как многие операции повторяются. Все еще не исправляет итерации по всем перестановкам, но это должно помочь.

Редактировать: Найден другой поток, который ответил на этот вопрос довольно хорошо. Как создать перестановки списка без «обратных дубликатов» в Python с использованием генераторов

Спасибо всем!

1 Ответ

0 голосов
/ 12 апреля 2020

Существует не более 10 возможных танцевальных подпрограмм, поэтому не более 3,6 млн. Перестановок и даже плохие алгоритмы, такие как «генерируй все» и «тестирование», будут выполнены очень быстро.

Если вам нужно быстрое решение для до 24 или около того подпрограмм, тогда я бы сделал это следующим образом ...

Учитывая подпрограммы танца R, в любой точке концерта, чтобы решить, какую подпрограмму вы можете выполнить дальше, вам нужно знать:

  1. Какие подпрограммы вы уже выполнили, потому что там вы не можете делать те, что дальше. Есть 2 R возможных наборов уже выполненных процедур; и
  2. Какая процедура выполнялась последней, поскольку это помогает определить стоимость следующей. Для этого существует не более R-1 возможных значений.

Таким образом, существует не более (R-2) * 2 R возможных сольных концертов ...

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

Например, если вы выполнили процедуры 5 и 6, с последним 5, то вы будете в состоянии (5,6): 5, и там было бы гранью к (3,5,6): 3, к которой вы могли бы добраться после выполнения процедуры 3.

Начиная с начального состояния "ничего не выполнено" (): -, используйте алгоритм Дейкстры, чтобы найти путь наименьшей стоимости к состоянию со всеми выполненными подпрограммами.

Общая сложность составляет O (R 2 * 2 R ) или около того, в зависимости от того, как именно вы его реализуете .

Для R = 10 R 2 * 2 R составляет ~ 100 000, что совсем не займет много времени. Для R = 24 это около 9 миллиардов, что займет довольно полминуты в довольно хорошем C ++.

...