كيفية التحقق مما إذا كانت التباديلات متساوية التكافؤ؟

Question

أنا أبحث عن وسيلة للتحقق إذا 2 التباديل (يمثلها قوائم) هي من نفس تعادل. وبعد لاحظ أنني لست مهتما إذا كانت حتى في أو غريب التكافؤ، فقط المساواة.

أنا جديد في بيثون وتردد الحل الساذج أدناه كرد. إنني أتطلع إلى Python Gurus تبين لي بعض الحيل الرائعة لتحقيق نفس الشيء في كود بيثون أقل وأكثر أناقة.

Answer 1

البديل البسيط للإجابة السابقة - نسخ بيرم 1، وحفظ البحث عن صفيف.

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

هنا هو قرصي من التعليمات البرمجية الخاصة بك

• استخدم قائمة () لنسخ بيرم 1 - وهذا يعني أنه يمكنك تمرير tuples، إلخ في الوظيفة، مما يجعله أكثر عام
• استخدام تعداد () في حلقة بدلا من Len (..) واختبئ الصفيف للحصول على رمز NEATER
• قم بإجراء perm1_map واحتفظ بها حتى الآن لإيقاف البحث عن o (n) باهظة الثمن على بيرم 1، وقائمة قائمة باهظة الثمن
• إرجاع المنطقي بشكل مباشر بدلا من إذا كنت ... عودة TRUE أخرى إرجاع خطأ

هاهو

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 (ن) في حجم التقليب. لاحظ أنه على الرغم من أن لدينا حلقة داخل حلقة، إلا أن الحلقة الداخلية يمكن أن تكرر مرة واحدة فقط لأي عنصر في التقليب.

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 حتى وكاذبة من أجل غريبة):

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

الحل مع القاموس هو Bugged. هذا هو إصدار التصحيح:

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