পাইথনে সমতুল্য ডমিনো জোড়া গুনুন (Number of Equivalent Domino Pairs in Python)

সমস্যা বিবরণ

ডমিনোর লিস্ট দেওয়া আছে। প্রতিটি ডমিনোর দুটি নম্বর থাকে। দুটি ডমিনো D[i]=[a,b] এবং D[j]=[c,d] সমতুল্য যদি (a=c এবং b=d) অথবা (a=d এবং b=c) - অর্থাৎ ডমিনো উল্টা দিয়ে মিলিয়ে দেখা হয়। সমতুল্য জোড়া (i,j) এর সংখ্যা বের করতে হবে যেখানে i < j।

উদাহরণ: [[1,2],[2,1],[3,4],[5,6],[4,3]] → আউটপুট ২ (জোড়া: [1,2]≡[2,1] এবং [3,4]≡[4,3])।

সমাধানের পদ্ধতি

1. প্রতিটি ডমিনো সর্ট করুন (ছোটটা আগে, বড়টা পরে) যাতে সমতুল্য ডমিনোগুলো একই রিপ্রেজেন্টেশন পায়।
2. ফ্রিকোয়েন্সি ম্যাপে (ডিকশনারি) প্রতিটি নরমালাইজড ডমিনোর কাউন্ট রাখুন।
3. প্রতিটি ফ্রিকোয়েন্সি f এর জন্য f*(f-1)/2 জোড়া যোগ করুন (কম্বিনেশন nC2)।
4. মোট যোগফল ফেরত দিন।

পাইথন উদাহরণ

class Solution(object):
    def numEquivDominoPairs(self, dominoes):
        freq = {}
        for d in dominoes:
            d.sort()
            key = tuple(d)
            freq[key] = freq.get(key, 0) + 1
        
        ans = 0
        for count in freq.values():
            ans += count * (count - 1) // 2
        return ans

ob1 = Solution()
print(ob1.numEquivDominoPairs([[1,2],[2,1],[3,4],[5,6],[4,3]]))

ইনপুট

[[1,2],[2,1],[3,4],[5,6],[4,3]]

আউটপুট

2

Counter ব্যবহার করে সংক্ষিপ্ত

from collections import Counter

def numEquivDominoPairs(dominoes):
    freq = Counter(tuple(sorted(d)) for d in dominoes)
    return sum(v * (v - 1) // 2 for v in freq.values())