Можно интересоваться чем-то как CSP или одна из другой теоретической алгебры для контакта с параллелизмом. Существуют библиотеки CSP для большинства языков, но если язык не был разработан для него, это требует, чтобы немного дисциплины использовало правильно. Но в конечном счете, каждый вид параллелизма/поточной обработки сводится к некоторым довольно простым основам: Избегайте совместно использованных изменяемых данных и поймите точно, когда и почему каждому потоку, вероятно, придется заблокироваться при ожидании другого потока. (В CSP просто не существуют совместно используемые данные. Каждый поток (или процесс в терминологии CSP) только позволили общаться с другими посредством блокирования каналов передачи сообщений. С тех пор нет никаких совместно используемых данных, условия состязания уходят. Так как передача сообщений блокируется, становится легко рассуждать о синхронизации и буквально доказать, что никакие мертвые блокировки не могут произойти.)
Другая хорошая практика, которую легче модифицировать в существующий код, должна присвоить приоритет или уровень к каждому привязывала Вашу систему, и удостовериться, что следующие правила последовательно сопровождаются:
После этих правил означают, что для мертвой блокировки просто невозможно произойти. Тогда просто необходимо волноваться об изменяемых совместно используемых данных.
A minor variant of the previous answer - copy perm1, and save array lookups.
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
Вот моя настройка вашего кода
Вот оно
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
Если мы объединим обе перестановки , результат будет иметь четную четность, если каждая перестановка имеет одинаковую четность, и нечетную четность, если они имеют разную четность. Итак, если мы решаем проблему четности , будет тривиально сравнить две разные перестановки.
Четность может быть определена следующим образом: выбрать произвольный элемент, найти позицию, в которую перестановка перемещает его, повторить пока вы не вернетесь к тому, с которого начали. Вы нашли цикл: перестановка поворачивает все эти элементы на одну позицию. Вам нужно на один обмен меньше, чем количество элементов в цикле, чтобы отменить его. Теперь выберите другой элемент, с которым вы еще не работали, и повторяйте, пока не увидите каждый элемент. Обратите внимание, что в целом вам потребовался один обмен на элемент минус один обмен за цикл.
Сложность по времени равна 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
Мое наивное решение:
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
Моя интуиция подсказывает мне, что простой подсчет различий между двумя перестановками даст вам на единицу больше, чем количество перестановок, необходимых для перехода от одного к другому. Это, в свою очередь, даст вам паритет.
Это означает, что вам вообще не нужно делать свопы в вашем коде.
Например:
ABCD, BDCA.
Есть три различия, следовательно, два свопа необходимы для переставляйте одно в другое, следовательно, у вас четная четность.
Другой:
ABCD, CDBA.
Есть четыре различия, следовательно, три перестановки, следовательно, нечетная четность.
Здесь слегка отредактирован ответ Уибла :
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