Как проверить, имеют ли перестановки равный паритет?

Question

Я ищу способ проверить, имеют ли 2 перестановки (представленные списками) одинаковые четности . Обратите внимание, что мне не интересно, являются ли они четными или нечетными четностями, просто равенством.

Я новичок в Python, и мое наивное решение приведено ниже в качестве ответа. Я с нетерпением жду, чтобы гуру Python продемонстрировали мне несколько интересных трюков, чтобы добиться того же в меньшем, более элегантном коде Python.

Answer 1

Если мы объединим обе перестановки, результат будет иметь четную четность, когда каждая перестановка имеет одинаковую четность, и нечетную четность, если они имеют разную четность. Так что, если мы решим проблему четности , будет тривиально сравнить две разные перестановки.

Четность можно определить следующим образом: выберите произвольный элемент, найдите позицию, на которую перестановка переместит это, повторяйте, пока не вернетесь к тому, с которого вы начали. Теперь вы нашли цикл: перестановка вращает все эти элементы вокруг одной позиции. Вам нужно на один обмен меньше, чем количество элементов в цикле, чтобы отменить его. Теперь выберите другой элемент, с которым вы еще не работали, и повторяйте, пока не увидите каждый элемент. Обратите внимание, что всего вам понадобился один своп на элемент минус один своп за цикл.

Сложность времени составляет O (N) в размере перестановки. Обратите внимание, что хотя у нас есть цикл внутри цикла, внутренний цикл может повторяться только один раз для любого элемента в перестановке.

def parity(permutation):
    permutation = list(permutation)
    length = len(permutation)
    elements_seen = [False] * length
    cycles = 0
    for index, already_seen in enumerate(elements_seen):
        if already_seen:
            continue
        cycles += 1
        current = index
        while not elements_seen[current]:
            elements_seen[current] = True
            current = permutation[current]
    return (length-cycles) % 2 == 0

def arePermsEqualParity(perm0, perm1):
    perm0 = list(perm0)
    return parity([perm0[i] for i in perm1])

Кроме того, просто для забавы, вот гораздо менее эффективная, но гораздо более короткая реализация функции четности, основанная на определении в Википедии (возвращающей True для четного и False для нечетного):

def parity(p):
    return sum(
        1 for (x,px) in enumerate(p)
          for (y,py) in enumerate(p)
          if x<y and px>py
        )%2==0

Answer 2

Вот мой твик вашего кода

• Используйте list () для копирования perm1 - это означает, что вы можете передавать кортежи и т. Д. В функцию, делая ее более общей
• Используйте enumerate () в цикле for вместо len (..) и поиска в массивах для более точного кода
• Создайте perm1_map и обновляйте его, чтобы остановить дорогой поиск O (N) в perm1 и дорогой фрагмент списка
• возвращает логическое значение напрямую, а не if ... return True иначе возвращает False

Вот оно

def arePermsEqualParity(perm0, perm1):
    """Check if 2 permutations are of equal parity.

    Assume that both permutation lists are of equal length
    and have the same elements. No need to check for these
    conditions.
    """
    perm1 = list(perm1) ## copy this into a list so we don't mutate the original
    perm1_map = dict((v, i) for i,v in enumerate(perm1))
    transCount = 0
    for loc, p0 in enumerate(perm0):
        p1 = perm1[loc]
        if p0 != p1:
            sloc = perm1_map[p0]                       # Find position in perm1
            perm1[loc], perm1[sloc] = p0, p1           # Swap in perm1
            perm1_map[p0], perm1_map[p1] = sloc, loc   # Swap the map
            transCount += 1
    # Even number of transpositions means equal parity
    return (transCount % 2) == 0

Answer 3

Незначительный вариант предыдущего ответа - скопируйте perm1 и сохраните результаты поиска в массиве.

def arePermsEqualParity(perm0, perm1):
    """Check if 2 permutations are of equal parity.

    Assume that both permutation lists are of equal length
    and have the same elements. No need to check for these
    conditions.
    """
    perm1 = perm1[:] ## copy this list so we don't mutate the original

    transCount = 0
    for loc in range(len(perm0) - 1):                         # Do (len - 1) transpositions
        p0 = perm0[loc]
        p1 = perm1[loc]
        if p0 != p1:
            sloc = perm1[loc:].index(p0)+loc          # Find position in perm1
            perm1[loc], perm1[sloc] = p0, p1          # Swap in perm1
            transCount += 1

    # Even number of transpositions means equal parity
    if (transCount % 2) == 0:
        return True
    else:
        return False

Answer 4

Мое наивное решение:

def arePermsEqualParity(perm0, perm1):
    """Check if 2 permutations are of equal parity.

    Assume that both permutation lists are of equal length
    and have the same elements. No need to check for these
    conditions.
    """

    transCount = 0
    for loc in range(len(perm0) - 1):                         # Do (len - 1) transpositions
        if perm0[loc] != perm1[loc]:
            sloc = perm1.index(perm0[loc])                    # Find position in perm1
            perm1[loc], perm1[sloc] = perm1[sloc], perm1[loc] # Swap in perm1
            transCount += 1

    # Even number of transpositions means equal parity
    if (transCount % 2) == 0:
        return True
    else:
        return False

Answer 5

Решение со словарем прослушивается. Это отладочная версия:

def arePermsEqualParity(perm0, perm1):
    """Check if 2 permutations are of equal parity.

    Assume that both permutation lists are of equal length
    and have the same elements. No need to check for these
    conditions.
    """
    perm1 = list(perm1) ## copy this into a list so we don't mutate the original
    perm1_map = dict((v, i) for i,v in enumerate(perm1))
    transCount = 0
    for loc, p0 in enumerate(perm0):
        p1 = perm1[loc]
        if p0 != p1:
            sloc = perm1_map[p0]                       # Find position in perm1
            perm1[loc], perm1[sloc] = p0, p1           # Swap in perm1
            perm1_map[p0], perm1_map[p1] = loc, sloc   # Swap the map
            transCount += 1
    # Even number of transpositions means equal parity
    return (transCount % 2) == 0

Единственное отличие состоит в том, что подстановка в словаре была выполнена неправильно.

Answer 6

Вот слегка переработанный Ответ Weeble :

def arePermsEqualParity(perm0, perm1):
    """Whether permutations are of equal parity."""
    return parity(combine(perm0, perm1))

def combine(perm0, perm1):
    """Combine two permutations into one."""
    return map(perm0.__getitem__, perm1)

def parity(permutation):
    """Return even parity for the `permutation`."""
    return (len(permutation) - ncycles(permutation)) % 2 == 0

def ncycles(permutation):
    """Return number of cycles in the `permutation`."""
    ncycles = 0
    seen = [False] * len(permutation)
    for i, already_seen in enumerate(seen):
        if not already_seen:
            ncycles += 1
            # mark indices that belongs to the cycle
            j = i 
            while not seen[j]: 
                seen[j] = True
                j = permutation[j]
    return ncycles

Answer 7

def equalparity(p,q):
    return sum([p[q[i]] > p[q[j]] for i in range(len(p)) for j in range(i)]) % 2 == 0

Answer 8

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

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

Например:

ABCD, BDCA.

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

Другой:

ABCD, CDBA.

Существует четыре различия, следовательно, три обмена, отсюда и странный паритет.