python - type - soup findall




Как проверить, симметричны ли две перестановки? (7)

Для двух перестановок 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

Вот простое решение, которое проходит мои тесты, а ваше:

  1. Сравните входы, ища подпоследовательность, которая не соответствует.
  2. Преобразование A путем транспонирования несогласованной подпоследовательности в соответствии с правилами. Соответствует ли результат B ?

Алгоритм O (N); нет встроенных циклов, явных или неявных.

На шаге 1 мне нужно определить случай, когда подстановочные подстановки смежны. Это может произойти только в середине строки, но мне было проще просто искать первый элемент перемещаемой части ( firstval ). Шаг 2 проще (и, следовательно, меньше подвержен ошибкам), чем явно проверять все ограничения.

def compare(A, B):
    same = True
    for i, (a, b) in enumerate(zip(A,B)):
        if same and a != b:  # Found the start of a presumed transposition
            same = False
            n = i
            firstval = a  # First element of the transposed piece
        elif (not same) and (a == b or b == firstval):  # end of the transposition
            m = i
            break

    # Construct the transposed string, compare it to B
    origin = A[n:m] 
    if n == 0:  # swap begins at the edge
        dest = A[-m:]
        B_expect = dest + A[m:-m] + origin
    else:
        dest = A[-m:-n]
        B_expect = A[:n] + dest + A[m:-m] + origin + A[-n:]

    return bool(B_expect == B)

Пример использования:

>>> compare("01234567", "45670123")
True

Бонус: Я считаю, что имя для этих отношений будет «симметричной транспозицией блока». ADCBE две подпоследовательности, взяв ABCDE в ADCBE . (См. Определение 4 here , я действительно нашел это путем googling «ADCBE»). Я добавил «симметричное» имя для описания условий длины.


Вот рабочее решение для вопроса:

def isSymmetric(A, B):
    L = len(A) #assume equivalent to len(B), modifying this would be as simple as checking if len(A) != len(B), return []
    la = L//2 # half-list length
    Al = A[:la]
    Ar = A[la:]
    Bl = B[:la]
    Br = B[la:]
    for i in range(la):
        lai = la - i #just to reduce the number of computation we need to perform
        for j in range(1, lai + 1):
            k = lai - j #same here, reduce computation
            if Al[i] != Br[k] or Ar[k] != Bl[i]: #the key for efficient computation is here: do not proceed unnecessarily
                 continue
            n = i #written only for the sake of clarity. i is n, and we can use i directly
            m = i + j
            if A[n:m] == B[L-m:L-n] and B[n:m] == A[L-m:L-n]: #possibly symmetric
                if A[0:n] == B[0:n] and A[m:L-m] == B[m:L-m] and A[L-n:] == B[L-n:]:
                    return [n, m]
    return []

Как вы уже упоминали, хотя идея выглядит просто, но на самом деле она довольно сложная . Однако, когда мы видим шаблоны, реализация выполняется прямолинейно.

Центральная идея решения - это одна линия:

if Al[i] != Br[k] or Ar[k] != Bl[i]: #the key for efficient computation is here: do not proceed unnecessarily

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

Чтобы найти решение, необходимо выполнить несколько шагов:

Во-первых , нам нужно разделить оба списка A и список B на два полных списка (называемые Al , Ar , Bl и Br ). Каждый полу-список будет содержать половину членов исходных списков:

Al = A[:la]
Ar = A[la:]
Bl = B[:la]
Br = B[la:]

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

Рассмотрим левую половину списка A , предположим, что у вас есть такой член:

Al = [al1, al2, al3, al4, al5, al6]

Мы можем представить, что для указанного списка есть соответствующий индексный список

Al  = [al1, al2, al3, al4, al5, al6]
iAl = [0,   1,   2,   3,   4,   5  ] #corresponding index list, added for explanation purpose

(Примечание: причина, по которой я упоминаю о представлении соответствующего списка индексов, упрощает объяснение)

Аналогично, мы можем представить, что в остальных трех списках могут быть одинаковые списки индексов. Назовем их iAr , iBl и iBr соответственно, и все они имеют одинаковые элементы с iAl .

Это индекс списков, который действительно имеет значение для нас, чтобы заглянуть - чтобы решить проблему.

Вот что я имею в виду: предположим, что у нас есть два параметра:

  1. index (давайте дадим ему имя переменной i , и я бы использовал символ ^ для текущего i )
  2. length (давайте присвоим ему имя переменной j , и я бы использовал символ == для визуального представления его значения длины)

для каждой оценки элемента индекса в iAl - тогда каждая оценка будет означать:

Учитывая значение индекса i и значение длины j в iAl , сделайте что-нибудь, чтобы определить, стоит ли проверять симметричную квалификацию, начиная с этого индекса и с этой длиной (Отсюда и появляется индекс поворота имени).

Теперь давайте возьмем пример одной оценки, когда i = 0 и j = 1 . Оценка может быть проиллюстрирована следующим образом:

iAl = [0, 1, 2, 3, 4, 5]
       ^ <-- now evaluate this index (i) = 0
       == <-- now this has length (j) of 1

Для того, чтобы индексы i и длина j были оценены далее, тогда у противоположного iBr должно быть одно и то же значение элемента с той же длиной, но с другим индексом ( iBr его индексом k )

iBr = [0, 1, 2, 3, 4, 5]
                      ^ <-- must compare the value in this index to what is pointed by iAl
                      == <-- must evaluate with the same length = 1

Например, для вышеуказанного случая это возможная «симметричная» перестановка только для двух списков Al-Br (мы рассмотрим другие два списка Ar-Bl позже):

Al = [0, x, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, x, 0]

В этот момент хорошо отметить, что

Это не стоит оценивать дальше, если даже указанное выше условие не соответствует действительности

И именно здесь вы получите алгоритм более эффективный ; то есть путем выборочной оценки только нескольких возможных случаев среди всех возможных случаев. И как найти несколько возможных случаев?

Путем поиска связи между индексами и длинами четырех списков. То есть для заданного индекса i и длины j в списке (скажем, Al ), какой должен быть индекс k в списке партнеров (в случае Br ). Длина для списка партнеров не обязательно должна быть найдена, потому что она такая же, как в списке (т.е. j ).

Имея это в виду, давайте теперь продолжим, чтобы увидеть, можем ли мы видеть больше шаблонов в процессе оценки .

Рассмотрим теперь эффект длины ( j ). Например, если мы должны оценивать из индекса 0 , но длина равна 2 то для сопоставления списка должен быть выбран другой индекс k чем когда длина равна 1

iAl = [0, 1, 2, 3, 4, 5]
       ^ <-- now evaluate this index (i) = 0
       ===== <-- now this has length (j) of 2

iBr = [0, 1, 2, 3, 4, 5]
                   ^ <-- must compare the value in this index to what is pointed by iAl
                   ===== <-- must evaluate with the same length = 2

Или, для иллюстрации выше, то, что действительно имеет значение fox i = 0 и y = 2 выглядит примерно так:

# when i = 0 and y = 2
Al = [0, y, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, 0, y] #y means to be checked later

Посмотрите, что приведенный выше шаблон немного отличается от i = 0 и y = 1 - позиция индекса для значения 0 в примере сдвинута:

# when i = 0 and y = 1, k = 5
Al = [0, x, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, x, 0]

# when i = 0 and y = 2, k = 4
Al = [0, y, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, 0, y] #y means to be checked later

Таким образом, сдвиг по длине, где должен быть проверен индекс списка партнеров. В первом случае, когда i = 0 и y = 1 , то k = 5 . Но во втором случае, когда i = 0 и y = 1 , то k = 4 . Таким образом, мы нашли отношение основополагающих индексов, когда мы изменили длину j для фиксированного индекса i (в данном случае равным 0 ) для индекса кодового списка k .

Теперь рассмотрим влияние индекса i с фиксированной длиной j для индекса кодового списка k . Например, давайте исправим длину как y = 4 , тогда для индекса i = 0 имеем:

iAl = [0, 1, 2, 3, 4, 5]
       ^ <-- now evaluate this index (i) = 0
       ========== <-- now this has length (j) of 4

iAl = [0, 1, 2, 3, 4, 5]
          ^ <-- now evaluate this index (i) = 1
          ========== <-- now this has length (j) of 4

iAl = [0, 1, 2, 3, 4, 5]
             ^ <-- now evaluate this index (i) = 2
             ========== <-- now this has length (j) of 4

#And no more needed

В приведенном выше примере можно видеть, что нам нужно оценить 3 возможности для данных i и j , но если индекс i изменяется на 1 с одинаковой длиной j = 4 :

iAl = [0, 1, 2, 3, 4, 5]
          ^ <-- now evaluate this index (i) = 1
          ========== <-- now this has length (j) of 4

iAl = [0, 1, 2, 3, 4, 5]
             ^ <-- now evaluate this index (i) = 2
             ========== <-- now this has length (j) of 4

Обратите внимание, что нам нужно всего лишь оценить 2 возможности. Таким образом, увеличение индекса i уменьшает количество возможных случаев, подлежащих оценке!

Со всеми найденными выше шаблонами мы почти нашли все основания, необходимые для того, чтобы алгоритм работал. Но для этого нам нужно найти связь между индексами, которые появляются в паре Al-Br для данного [i, j] => [k, j] с индексами в паре Ar-Bl для тех же [i, j] .

Теперь мы можем видеть, что они просто отражают отношения, которые мы нашли в паре Al-Br !

(ИМХО, это действительно красиво! И, следовательно, я думаю, что термин «симметричная» перестановка находится недалеко от истины)

Например, если мы имеем следующую пару Al-Br оцененную с i = 0 и y = 2

Al = [0, y, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, 0, y] #y means to be checked later

Затем, чтобы сделать его симметричным , мы должны иметь соответствующий Ar-Bl :

Ar = [x, x, x, x, 3, y] #x means don't care for now
Bl = [3, y, x, x, x, x] #y means to be checked later

Al-Br пары Al-Br зеркалирует (или является симметричным) индексирование пары Ar-Bl !

Поэтому, объединяя весь шаблон, который мы нашли выше, теперь мы можем найти опорные индексы для оценки Al , Ar , Bl и Br .

Нам нужно сначала проверить значения списков в сводном индексе . Если значения оценок в сводных индексах Al , Ar , Bl и Br совпадают в оценке тогда и только тогда, нам нужно проверить симметричные критерии (тем самым делая вычисления эффективными!).

Введя все вышеперечисленные знания в код, в результате получается код Python for-loop для проверки симметричности:

for i in range(len(Al)): #for every index in the list
    lai = la - i #just simplification
    for j in range(1, lai + 1): #get the length from 1 to la - i + 1
        k = lai - j #get the mirror index
        if Al[i] != Br[k] or Ar[k] != Bl[i]: #if the value in the pivot indexes do not match
             continue #skip, no need to evaluate
        #at this point onwards, then the values in the pivot indexes match
        n = i #assign n
        m = i + j #assign m
        #test if the first two conditions for symmetric are passed
        if A[n:m] == B[L-m:L-n] and B[n:m] == A[L-m:L-n]: #possibly symmetric
            #if it passes, test the third condition for symmetric, the rests of the elements must stay in its place
            if A[0:n] == B[0:n] and A[m:L-m] == B[m:L-m] and A[L-n:] == B[L-n:]:                   
                return [n, m] #if all three conditions are passed, symmetric lists are found! return [n, m] immediately!
        #passing this but not outside of the loop means 
        #any of the 3 conditions to find symmetry are failed
        #though values in the pivot indexes match, simply continue
return [] #nothing can be found - asymmetric lists

И вот вам с симметричным тестом!

(Хорошо, это довольно сложная задача, и мне нужно время, чтобы понять, как это сделать.)


Еще одна версия:

def compare(a, b):
    i_zip = list(enumerate(zip(a, b)))
    llen = len(a)
    hp = llen // 2

    def find_index(i_zip):
        for i, (x, y) in i_zip:
            if x != y:
                return i
        return i_zip[0][0]

    # n and m are determined by the unmoved items:
    n = find_index(i_zip[:hp])
    p = find_index(i_zip[hp:])
    m = llen - p
    q = llen - n
    # Symmetric?
    if a[:n] + a[p:q] + a[m:p] + a[n:m] + a[q:] != b:
        return None
    return n, m

Это решение основано на:

  1. Все допустимые пары пар A, B, соблюдающие требование симметрии, будут иметь следующую структуру:

    A = P1 + P2 + P3 + P4 + P5 B = P1 + P4 + P3 + P2 + P5 ^n ^m ^hp ^p ^q <- indexes

    , len (P1) == len (P5) и len (P2) == len (P4)

  2. Поэтому 3 последних строки указанной функции будут определять правильное решение при условии правильного определения индексов n , m . ( p & q - только зеркальные индексы m & n )
  3. Поиск n - это вопрос определения того, когда элементы A и B начинают расходиться. Следующий же метод применяется для нахождения p начиная с середины hp . m является просто зеркальным индексом p . Все задействованные индексы найдены, и решение появляется.

Составьте список (ds) индексов, в которых отличаются две половины из двух списков. Возможный n - первый такой индекс, последний такой индекс - m - 1. Проверьте правильность симметрии. len (ds) == m - n гарантирует отсутствие пробелов.

import itertools as it
import operator as op

def test(a, b):
    sz = len(a)
    ds = list(it.compress(it.count(), map(op.ne, a[:sz//2], b[:sz//2])))
    n,m = ds[0], ds[-1]+1
    if a[n:m] == b[sz-m:sz-n] and b[n:m] == a[sz-m:sz-n] and len(ds) == m - n:
        return n,m
    else:
        return None

Я переписал код без некоторой сложности (и ошибок).

def test_o_o(a, b):

    L = len(a)
    H = L//2
    n, m = 0, H-1

    # find the first difference in the left-side
    while n < H:
        if a[n] != b[n]: break
        n += 1
    else: return

    # find the last difference in the left-side
    while m > -1:
        if a[m] != b[m]: break 
        m -= 1
    else: return

    # for slicing, we want end_index+1
    m += 1

    # compare each slice for equality
    # order: beginning, block 1, block 2, middle, end
    if (a[0:n] == b[0:n] and \
        a[n:m] == b[L-m:L-n] and \
        b[n:m] == a[L-m:L-n] and \
        a[m:L-m] == b[m:L-m] and \
        a[L-n:L] == b[L-n:L]):

        return n, m

Реализация является элегантной и эффективной.

break в else: return структуры else: return гарантируют, что функция вернется в максимально возможной точке. Они также подтверждают, что значения n и m были установлены в допустимые значения, но это не представляется необходимым при явной проверке срезов. Эти линии могут быть удалены без заметного влияния на время.

Явное сравнение срезов также будет короткозамкнуто, как только вы оцените значение False .

Первоначально я проверил, существовала ли перестановка путем преобразования b в a :

b = b[:]
b[n:m], b[L-m:L-n] = b[L-m:L-n], b[n:m]
if a == b:
   return n, m

Но это медленнее, чем прямое сравнение срезов. Сообщите мне, если алгоритм не говорит сам за себя, и я могу предложить дополнительное объяснение (возможно, даже доказательство) относительно того, почему он работает и минимален.


Я попытался реализовать 3 разных алгоритма для этой задачи. Все они имеют сложность времени O (N) и требуют O (1) дополнительного пространства. Интересный факт: все остальные ответы (известные до сих пор) реализуют 2 из этих алгоритмов (хотя они не всегда сохраняют оптимальную асимптотическую сложность времени / пространства). Вот описание высокого уровня для каждого алгоритма:

Алгоритм A

  1. Сравните списки, группы «не равные» интервалы, убедитесь, что есть ровно два таких интервала (со специальным случаем, когда интервалы встречаются посередине).
  2. Убедитесь, что «неравные» интервалы расположены симметрично, а их содержимое также «симметрично».

Алгоритм B

  1. Сравните первые половины списков, чтобы угадать, где находятся «интервалы, которые нужно обменять».
  2. Проверьте, является ли содержимое этих интервалов «симметричным». И убедитесь, что списки равны за пределами этих интервалов.

Алгоритм C

  1. Сравните первые половины списков, чтобы найти первый несоответствующий элемент.
  2. Найдите этот несоответствующий элемент первого списка во втором. Это указывает на положение «интервалов, которые нужно обменять».
  3. Проверьте, является ли содержимое этих интервалов «симметричным». И убедитесь, что списки равны за пределами этих интервалов.

Для шага 1 каждого алгоритма есть две альтернативные реализации: (1) использование itertools и (2) использование простых циклов (или списков). itertools эффективны для длинных списков, но относительно короткие в коротких списках.

Вот алгоритм C с первым шагом, реализованным с использованием itertools. Это выглядит проще, чем другие два алгоритма (в конце этого сообщения). И это довольно быстро, даже для коротких списков:

import itertools as it
import operator as op

def test_C(a, b):
    length = len(a)
    half = length // 2
    mismatches = it.imap(op.ne, a, b[:half]) # compare half-lists

    try:
        n = next(it.compress(it.count(), mismatches))
        nr = length - n
        mr = a.index(b[n], half, nr)
        m = length - mr
    except StopIteration: return None
    except ValueError: return None

    if a[n:m] == b[mr:nr] and b[n:m] == a[mr:nr] \
            and a[m:mr] == b[m:mr] and a[nr:] == b[nr:]:
        return (n, m)

Это можно сделать, используя в основном itertools:

def test_A(a, b):
    equals = it.imap(op.eq, a, b) # compare lists
    e1, e2 = it.tee(equals)
    l = it.chain(e1, [True])
    r = it.chain([True], e2)
    borders = it.imap(op.ne, l, r) # delimit equal/non-equal intervals
    ranges = list(it.islice(it.compress(it.count(), borders), 5))

    if len(ranges) == 4:
        n1, m1 = ranges[0], ranges[1]
        n2, m2 = ranges[2], ranges[3]
    elif len(ranges) == 2:
        n1, m1 = ranges[0], len(a) // 2
        n2, m2 = len(a) // 2, ranges[1]
    else:
        return None

    if n1 == len(a) - m2 and m1 == len(a) - n2 \
            and a[n1:m1] == b[n2:m2] and b[n1:m1] == a[n2:m2]:
        return (n1, m1)

Высокоуровневое описание этого алгоритма уже представлено в комментариях OP by @j_random_hacker. Вот несколько деталей:

Начните с сравнения списков:

A  0 1 2 3 4 5 6 7
B  0 5 6 3 4 1 2 7
=  E N N E E N N E

Затем найдите границы между равными / не равными интервалами:

=  E N N E E N N E
B  _ * _ * _ * _ *

Затем определите диапазоны для неравных элементов:

B  _ * _ * _ * _ *
    [1 : 3] [5 : 7]

Затем проверьте, есть ли ровно 2 диапазона (со специальным случаем, когда оба диапазона встречаются посередине), сами диапазоны симметричны и их содержимое тоже.

Другой альтернативой является использование itertools для обработки только половины каждого списка. Это позволяет немного упростить (и немного быстрее) алгоритм, потому что нет необходимости обрабатывать специальный случай:

def test_B(a, b):
    equals = it.imap(op.eq, a, b[:len(a) // 2]) # compare half-lists
    e1, e2 = it.tee(equals)
    l = it.chain(e1, [True])
    r = it.chain([True], e2)
    borders = it.imap(op.ne, l, r) # delimit equal/non-equal intervals
    ranges = list(it.islice(it.compress(it.count(), borders), 2))

    if len(ranges) != 2:
        return None

    n, m = ranges[0], ranges[1]
    nr, mr = len(a) - n, len(a) - m

    if a[n:m] == b[mr:nr] and b[n:m] == a[mr:nr] \
            and a[m:mr] == b[m:mr] and a[nr:] == b[nr:]:
        return (n, m)

Я считаю, что следующий псевдокод должен работать:

  1. Найдите первый элемент i для которого A[i] != B[i] , положим n = i . Если такого элемента нет, верните success . Если n >= L/2 , возврат fail .
  2. Найдите первый элемент i > n для которого A[i] == B[i] , задайте m = i . Если такого элемента или m > L/2 , не задавайте m = L/2 .
  3. Проверьте, что A[0:n] == B[0:n] , A[n:m] == B[Lm:Ln] , B[n:m] == A[Lm:Ln] , A[m:Lm] == B[m:Lm] и A[Ln:L] == B[Ln:L] . Если все верно, верните success . В противном случае возврат fail .

Сложность - это O (n), которая должна быть минимально возможной, поскольку всегда нужно сравнивать все элементы в списках.





algorithm