10

2つの順列（リストで表される）が同じパリティであるかどうかを確認する方法を探しています。それらが偶数または奇数のパリティであるかどうかは興味がなく、等しいだけであることに注意してください。

私はPythonを初めて使用しますが、私の素朴な解決策を以下に返信します。私はPythonの達人が、より少なく、よりエレガントなPythonコードで同じことを達成するためのいくつかのクールなトリックを見せてくれるのを楽しみにしています。

4

8 に答える 8

7

両方の順列を組み合わせると、各順列のパリティが同じ場合は偶数のパリティになり、異なるパリティの場合は奇数のパリティになります。したがって、パリティの問題を解決する場合、 2つの異なる順列を比較するのは簡単です。

パリティは次のように決定できます。任意の要素を選択し、順列がこれを移動する位置を見つけ、最初の要素に戻るまで繰り返します。これで、サイクルが見つかりました。順列は、これらすべての要素を1つの位置だけ回転させます。元に戻すには、サイクル内の要素数より1つ少ないスワップが必要です。次に、まだ扱っていない別の要素を選択し、すべての要素が表示されるまで繰り返します。合計で、要素ごとに1つのスワップから、サイクルごとに1つのスワップを引いたものが必要であることに注意してください。

時間計算量は、順列のサイズでO（N）です。ループ内にループがありますが、内側のループは、順列内の任意の要素に対して1回しか反復できないことに注意してください。

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
于 2009-10-01T15:15:13.040 に答える
6

これがあなたのコードの私の微調整です

  • list（）を使用してperm1をコピーします-これは、タプルなどを関数に渡して、より汎用的にすることができることを意味します
  • len（..）の代わりにforループでenumerate（）を使用し、より適切なコードの配列ルックアップを使用します
  • perm1_mapを作成し、それを最新の状態に保つことで、perm1での高価なO（N）検索と、高価なリストスライスを停止します。
  • if ...ではなく、ブール値を直接返します。trueを返すelseは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
于 2009-10-01T12:14:01.550 に答える
5

前の回答のマイナーな変形-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
于 2009-10-01T10:26:33.620 に答える
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
于 2009-10-01T10:12:53.707 に答える
2

少しリファクタリングされた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
于 2009-10-02T22:41:14.680 に答える
2

辞書を使用したソリューションにはバグがあります。これはデバッグバージョンです：

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

唯一の違いは、辞書のスワップが正しく行われなかったことです。

于 2010-11-18T14:13:08.657 に答える
0 
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
于 2011-06-07T20:49:32.653 に答える
0

私の直感によると、2つの順列の違いを数えるだけで、一方から他方に取得する必要のあるスワップの数よりも1つ多くなります。これにより、パリティが得られます。

これは、コードでスワップを行う必要がまったくないことを意味します。

例えば：

ABCD, BDCA.

3つの違いがあるため、一方を他方に並べ替えるには2つのスワップが必要です。したがって、パリティが均等になります。

別：

ABCD, CDBA.

4つの違い、つまり3つのスワップ、つまり奇数パリティがあります。

于 2009-10-01T11:46:40.460 に答える