В эпизоде ​​Futurama «Узник Бенды» члены экипажа обмениваются телами друг с другом, с тем уловкой, что ни одна пара тел не может поменять свой разум более одного раза.

Вызов

Напишите программу или функцию, которая принимает действительный набор обменов разума и тела, которые уже произошли, и выводит законный набор обменов, которые вернут каждый разум в его первоначальное тело. Идентификаторы для этих коллекций разум-тело должны быть строками, которые не будут содержать переводы строки. Вы можете добавить до двух (с разными именами) людей, у которых ранее не было свопов в группу ввода. (Доказательство того, что вам нужно не более 2 дополнительных тел). Однако вы должны добавить минимальное количество людей, необходимое для решения проблемы.

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

Примеры

[('A','B'),('C','D')] -> [('A','C'),('B','D'),('A','D'),('B','C')]

['A','B'] -> ['C','D','A','C','B','D','A','D','B','C']

[('A','B'),('C','D'),('A','C'),('A','D')] -> [('B', 'E'), ('A', 'E'), ('C', 'B'), ('C', 'E')]

"A\nB\nC\nD\n" -> "A\nC\nB\nD\nA\nD\nB\nC\n"

Тот из шоу:

[("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Phillip","John"),("Hermes","Turanga")]

Решение шоу, приведенное ниже, недействительно:

[("Clyde","Phillip"),("Ethan","John"),("Clyde","John"),("Ethan",Phillip"),("Clyde","Hubert"),("Ethan","Wash Bucket"),("Clyde","Leela"),("Ethan","Nikolai"),("Clyde","Hermes"),("Ethan","Bender"),("Clyde","Amy"),("Ethan","Hubert"),("Clyde","Wash Bucket")]

Это неверно, потому что Итан и Клайд не нужны из-за того, как мало Фрая Филиппа, Зойдберга Джона и Гермеса Гермеса использовали машину. Действительное решение для этого случая предоставлено ниже:

[("Philip","Hubert"),("John","Wash Bucket"),("Philip","Turanga"),("John","Nikolai"),("Philip","Hermes"),("John","Bender"),("Philip","Amy"),("John","Hubert"),("Philip","Wash Bucket")]

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

Python 3: 328 символов (медленно), 470 символов (быстро)

Наверное, слишком долго для серьезного ответа.

Медленный и короткий код:

from itertools import*
def d(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 n=list(n)
 while 1:
  for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)):
   u=n[:];j=0
   for s in Q:d(u,s)
   for s in t:
    j+=1;d(u,s)
    if n==u:return t[:j]
  n+=[''.join(n)]

d(u,s)применяет своп sк u. В методе main f(Q)я сначала генерирую список всех людей, nиспользующих операции над множествами, и преобразовываю результат обратно в список. while 1-Loop, конечно , не в петле бесконечности. В ней я тоже пытаюсь решить проблему, используя людей, в которых я работаю n. Если это не удастся, я добавлю еще одного человека, объединив все имена n+=[''.join(n)]. Поэтому while 1-loop выполняется максимум 3 раза (см. Доказательство в вопросе).

Решение проблемы осуществляется грубо. Я генерирую все перестановки, которые являются законными, и пробую все перестановки for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)). Если каждый человек находится в своем собственном теле, я возвращаю последовательность перестановок.

Применение:

print(f([('A','B'),('C','D')]))
print(f([('A','B')]))
print(f([('A','B'),('C','D'),('A','C'),('A','D')]))

Пример из футурамы занимает слишком много времени. Есть 9 человек, так что есть 36 возможных обменов, и 28 из них являются законными. Итак, их 26! правовые перестановки.

Более быстрый код

def w(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 while 1:
  n=list(n);u=n[:];l=len(n)
  for s in Q:w(u,s)
  for d in range((l*l-l)//2-len(Q)+1):r(n,u,Q,[],d)
  n+=[''.join(n)]
def r(n,u,Q,t,d):
 m=0;v=u[:];l=len(u)
 for i in range(l):
  if n[i]!=v[i]:m+=1;w(v,(n[i],v[i]))
 if m<1:print(t);exit()
 for i in range(l*l):
  s=n[i//l],n[i%l]
  if m<=d and i//l<i%l and not set([s,s[::-1]])&set(Q+t):v=u[:];w(v,s);r(n,v,Q,t+[s],d-1)

Функция f(Q)имеет итеративный подход углубления. Сначала он пробует глубину = 0, затем глубину = 1, пока глубина = (l * ll) // 2-len (Q), которая является максимальным числом допустимых ходов. Как и более медленный код, он добавляет другого человека и пытается снова.

Рекурсивная функция r(n,u,Q,t,d)пытается решить текущую позицию uс помощью dсвопов. nэто решенная позиция, Qвходные ходы и tходы уже сделаны. Сначала он рассчитывает нижнюю границу mнеобходимых свопов (решая вопрос с государством с помощью легальных и нелегальных свопов). Если m== 0, все люди находятся в правильном теле, поэтому оно печатает решение t. В противном случае он пробует все возможные перестановки s, если m<d(сокращение), d>1(которое уже включено m<d, i//l<i%l(не разрешать перестановки, такие как ('A','A')или ('A','B')и ('B','A')) и not set([s,s[::-1]])&set(Q+t)( sеще не было выполнено).

Применение:

f([("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Philip","John"),("Hermes","Turanga")])

Он находит оптимальные замены для проблемы с футурамой примерно за 17 секунд на моем ноутбуке с использованием pypy и около 2 минут без pypy. Обратите внимание, что оба алгоритма выдают разные решения при вызове его с одним и тем же параметром. Это из-за алгоритма хеширования питона set. nхранит человека каждый раз в другом порядке. Поэтому алгоритм может быть быстрее или медленнее с каждым прогоном.

Редактировать: исходный контрольный пример был неправильным, исправленный контрольный пример имеет оптимальное решение 9 вместо 10, и, следовательно, быстрее. 2 секунды с пыпи, 7 секунд без.