Учитывая, что 8 букв можно переставить примерно 40 тысячами можно просто запустить поиск в ширину, сохранить для всех перестановок то, из какой строчки они получились, и потом восстановить ответ для строчки abcdefgh.
while not to_process.empty(): s, prev = to_process.get() if s in prec: continue for i in range(7): for j in range(i + 1, 8): if i == 0: next_s = s[j::-1] + s[j+1:] else: next_s = s[:i] + s[j:i-1:-1] + s[j+1:] if next_s not in prec: to_process.put((next_s, s)) prec[s] = prev
current = "abcdefgh" print(current) while prec[current] is not None: current = prec[current] print(current)
В результате экономического развития в пореформенный период (особенно промышленного подъема 90-х годов XIX в. , завершился к 1880-1890 гг. ) окончательно сложилась система российского капитализма. Это выражалось в росте предпринимательства и капиталов, совершенствовании производства, его технологическом перевооружении, увеличении количества наемной рабочей силы во всех сферах народного хозяйства. Одновременно с другими капиталистическими странами в России происходила вторая техническая революция (ускорение производства средств производства, широкое использование электричества и других достижений современной науки) , совпавшая с индустриализацией. Из отсталой аграрной страны Россия к началу XX в. стала аграрно-индустриальной державой (82 % занято в сельском хозяйстве) . По объему промышленной продукции она вошла в пятерку крупнейших государств (Англия, Франция, США и Германия) и все глубже втягивалась в мировую систему хозяйства.
Код на python 3:
from queue import Queue
to_process = Queue()
to_process.put(("edghcbfa", None))
prec = {}
while not to_process.empty():
s, prev = to_process.get()
if s in prec:
continue
for i in range(7):
for j in range(i + 1, 8):
if i == 0:
next_s = s[j::-1] + s[j+1:]
else:
next_s = s[:i] + s[j:i-1:-1] + s[j+1:]
if next_s not in prec:
to_process.put((next_s, s))
prec[s] = prev
current = "abcdefgh"
print(current)
while prec[current] is not None:
current = prec[current]
print(current)
Вывод программы:
abcdefgh
edcbafgh
edcbhgfa
edbchgfa
edghcbfa
Соответственно, ответ такой:
G B
B C
H A
E A