Учитывая, что 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)
Учитывая, что 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)
Объяснение:
1)выливаем из 8-литрового в 3-хлитровую
2).Эту 3-хлитровую выливаем в 5-тилитровый сосуд
3))выливаем из 8-литрового в 3-хлитровую
4).Эту 3-хлитровую выливаем в 5-тилитровый сосуд, до того, пока он становится полным.
5).Этот 5-тилиртовый сосуд (молоко) выливаем полностью в 8-илитровую
6).1 литр молока, который находится в 3-хлитровом сосуде, выливаем в 5-илитровый.
7)выливаем из 8-литрового в 3-хлитровую
8)это молоко из 3-хлитрого выливаем в 5-тилитровый. Там стал 4 литра молока!
В 8-милитровом сосуде также 4 литра молока.