Учитывая две перестановки A
и B
из L
разных элементов, L
четна, назовем эти перестановки "симметричными" (для отсутствия лучшего термина), если существуют n
и m
, m > n
, например (в нотации на питоне):
- A[n:m] == B[L-m:L-n]
- B[n:m] == A[L-m:L-n]
- all other elements are in place
Неформально рассмотрим
A = 0 1 2 3 4 5 6 7
Возьмите любой его фрагмент, например 1 2
. Он начинается со второго индекса, а его длина равна 2. Теперь возьмите симметричный ему срез: он заканчивается в предпоследнем индексе и также длинна 2 символа, поэтому он 5 6
. Переключение этих фрагментов дает
B = 0 5 6 3 4 1 2 7
Теперь A
и B
являются "симметричными" в указанном выше смысле (n=1, m=3
). С другой стороны,
A = 0 1 2 3 4 5 6 7
B = 1 0 2 3 4 5 7 6
не являются "симметричными" (нет n,m
с указанными выше свойствами).
Как я могу написать алгоритм в python, который обнаруживает, что две заданные перестановки (= списки) являются "симметричными", и если да, найдите n
и m
? Для простоты рассмотрим только четный L
(так как нечетный случай может быть тривиально уменьшен до четного путем исключения среднего фиксированного элемента) и считать правильные входы (set(A)==set(B), len(set(A))==len(A)
).
(У меня нет проблем переубедить все возможные симметрии, но искать что-то умнее и быстрее).
Интересный факт: число симметричных перестановок для данного L
есть Треугольное число.
Я использую этот код, чтобы проверить ваши ответы.
Обновление Bounty: здесь много отличных ответов. @Решение Jared Goguen является самым быстрым.
Окончательные тайминги:
testing 0123456789 L= 10
test_alexis ok in 15.4252s
test_evgeny_kluev_A ok in 30.3875s
test_evgeny_kluev_B ok in 27.1382s
test_evgeny_kluev_C ok in 14.8131s
test_ian ok in 26.8318s
test_jared_goguen ok in 10.0999s
test_jason_herbburn ok in 21.3870s
test_tom_karzes ok in 27.9769s