순열의 패리티가 동일한지 확인하는 방법은 무엇입니까?

Question

2인지 확인하는 방법을 찾고 있습니다. 순열 (목록으로 표시됨)은 같은 동등.나는 관심이 없습니다. 심지어 또는 이상한 패리티, 그냥 평등.

저는 Python을 처음 접했고 저의 순진한 솔루션이 아래에 답변으로 제공됩니다.나는 Python 전문가들이 나에게 더 작고, 더 우아한 Python 코드로 동일한 결과를 얻을 수 있는 몇 가지 멋진 트릭을 보여줄 것을 기대하고 있습니다.

Answer 1

이전 답변의 사소한 변형 - 복사 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 2

다음은 코드 조정입니다

• List ()를 사용하여 Perm1을 복사합니다 - 이것은 튜플 등을 함수로 전달하여 더 일반적인 것을 만들 수 있음을 의미합니다.
• Len (..) 대신 For Loop에서 enumerate ()를 사용하고 깔끔한 코드의 배열 조회
• Perm1_map을 만들고 최신 상태로 유지하여 값 비싼 O (N) 검색을 중지하고 비싼 목록 슬라이스
• if 대신 부울을 직접 반환 ... retud 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

Answer 3

두 순열을 결합하면 결과는 각 순열의 패리티가 동일할 때 짝수 패리티를 가지며, 서로 다른 패리티를 가질 경우 홀수 패리티를 갖게 됩니다.그래서 문제를 해결하면 패리티 문제 두 가지 다른 순열을 비교하는 것은 쉽지 않습니다.

동등 다음과 같이 결정될 수 있습니다:임의의 요소를 선택하고 순열이 이를 이동하는 위치를 찾은 다음 시작한 요소로 돌아갈 때까지 반복합니다.이제 다음과 같은 주기를 찾았습니다.순열은 이러한 모든 요소를 ​​한 위치씩 회전시킵니다.실행 취소하려면 주기의 요소 수보다 적은 스왑이 필요합니다.이제 아직 다루지 않은 다른 요소를 선택하고 모든 요소를 ​​볼 때까지 반복하세요.전체적으로 요소당 하나의 스왑에서 사이클당 하나의 스왑을 뺀 값이 필요하다는 점을 확인하세요.

시간 복잡도는 순열 크기에서 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])

또한 재미를 위해 Wikipedia의 정의를 기반으로 하는 패리티 함수의 훨씬 덜 효율적이지만 훨씬 더 짧은 구현이 있습니다(짝수인 경우 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 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

여기에 약간 리팩토링이 있습니다 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 6

사전이있는 솔루션이 버그를 띠게됩니다. 이것은 디버그 버전입니다.

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 7

내 직관은 두 순열의 차이를 계산하면 스왑 횟수가 하나 더 줄어들게 될 것이라고 말합니다. 이것은 차례로 당신에게 패리티를 줄 것입니다.

이것은 코드에서 스왑을 전혀 수행 할 필요가 없음을 의미합니다.

예를 들어:

ABCD, BDCA.

세 가지 차이점이 있으므로 다른 스왑을 다른 스왑에 분출시키기 위해 두 가지 스왑이 필요하므로 패리티도 있습니다.

또 다른:

ABCD, CDBA.

네 가지 차이점이 있으므로 세 가지 스왑이있어 이상한 패리티가 있습니다.

Answer 8

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