python beautifulsoup - Как проверить, симметричны ли две перестановки?




example html (9)

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

Answers

Составьте список (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

Это правильно:

Br = B[L//2:]+B[:L//2]
same_full = [a==b for (a,b) in zip(A, Br)]
same_part = [a+b for (a,b) in zip(same_full[L//2:], same_full[:L//2])]

for n, vn in enumerate(same_part):
    if vn != 2:
        continue
    m = n
    for vm in same_part[n+1:]:
        if vm != 2:
            break
        m+=1

    if m>n:
        print("n=", n, "m=", m+1)

Я уверен, что вы можете сделать подсчет бит, но ... meh


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

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 . Все задействованные индексы найдены, и решение появляется.

Вот решение O (N), которое передает тестовый код:

def sym_check(a, b):
    cnt = len(a)

    ml = [a[i] == b[i] for i in range(cnt)]

    sl = [i for i in range(cnt) if (i == 0 or ml[i-1]) and not ml[i]]
    el = [i+1 for i in range(cnt) if not ml[i] and (i == cnt-1 or ml[i+1])]

    assert(len(sl) == len(el))

    range_cnt = len(sl)

    if range_cnt == 1:
        start1 = sl[0]
        end2 = el[0]

        if (end2 - start1) % 2 != 0:
            return None

        end1 = (start1 + end2) // 2
        start2 = end1

    elif range_cnt == 2:

        start1, start2 = sl
        end1, end2 = el

    else:
        return None

    if end1 - start1 != end2 - start2:
        return None

    if start1 != cnt - end2:
        return None

    if a[start1:end1] != b[start2:end2]:
        return None

    if b[start1:end1] != a[start2:end2]:
        return None

    return start1, end1

Я тестировал его только с Python 2, но я считаю, что он также будет работать с Python 3.

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


Я построю карту, где символы находятся в списке B, а затем используйте это, чтобы определить подразумеваемые поддиапазоны в списке A. После того, как у меня есть поддиапазоны, я могу проверить работоспособность некоторых данных и сравнить их.

Если A[i] == x , то где x появляется в B? Вызовите эту позицию p .

Я знаю, что i , начало левого поддиапазона.

Я знаю L (= len(A)) , поэтому я знаю Li , конец правого поддиапазона.

Если я знаю p , то я знаю подразумеваемый запуск правого поддиапазона, предполагая, что B [p] и A [i] являются началом симметричной пары диапазонов. Таким образом, L - m OP будет p если списки были симметричными.

Установка Lm == p дает мне m , поэтому у меня есть все четыре конечных точки.

Испытания на чувствительность:

  • n и m находятся в левой половине списка (ов)
  • n <= m (примечание: OP не запрещает n == m)
  • Ln находится в правой половине списка (вычисляется)
  • Lm находится в правой половине (это хорошая проверка для быстрого сбоя)

Если все эти проверки, сравните A [left] == ​​B [right] и B [left] == ​​A [right]. Вернитесь left если это правда.

def find_symmetry(a:list, b:list) -> slice or None:

    assert len(a) == len(b)
    assert set(a) == set(b)
    assert len(set(a)) == len(a)

    length = len(a)
    assert length % 2 == 0

    half = length // 2
    b_loc = {bi:n for n,bi in enumerate(b)}

    for n,ai in enumerate(a[:half]):
        L_n = length - 1 - n    # L - n
        L_m = b_loc[ai]         # L - m (speculative)

        if L_m < half:         # Sanity: bail if on wrong side
            continue

        m = b_loc[a[L_n]]  # If A[n] starts range, A[m] ends it.

        if m < n or m > half:   # Sanity: bail if backwards or wrong side
            continue

        left = slice(n, m+1)
        right = slice(L_m, L_n+1)

        if a[left] == b[right] and \
            b[left] == a[right]:
            return left

    return None

res = find_symmetry(
        [ 10, 11, 12, 13, 14, 15, 16, 17, ],
        [ 10, 15, 16, 13, 14, 11, 12, 17, ])
assert res == slice(1,3)

res = find_symmetry(
    [ 0, 1, 2, 3, 4, 5, 6, 7, ],
    [ 1, 0, 2, 3, 4, 5, 7, 6, ])
assert res is None

res = find_symmetry("abcdefghijklmn", "nbcdefghijklma")
assert res == slice(0,1)

res = find_symmetry("abcdefghijklmn", "abjklfghicdmen")
assert res == slice(3,4)

res = find_symmetry("abcdefghijklmn", "ancjkfghidelmb")
assert res == slice(3,5)

res = find_symmetry("abcdefghijklmn", "bcdefgaijklmnh")
assert res is None

res = find_symmetry("012345", "013245")
assert res == slice(2,3)

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

  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), которая должна быть минимально возможной, поскольку всегда нужно сравнивать все элементы в списках.


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

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

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


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

  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»). Я добавил «симметричное» имя для описания условий длины.


Словарь в python имеет метод get ('key', default). Таким образом, вы можете просто установить значение по умолчанию, если нет ключа.

values = {...}
myValue = values.get('Key', None)




python algorithm