পাইথন প্রোগ্রাম: বাইডায়রেকশনাল টাপল জোড়ার সংখ্যা গুননা

ভূমিকা

একটি টাপল তালিকায় বাইডায়রেকশনাল (bidirectional) জোড়া মানে যদি (a, b) এবং (b, a) দুটি টাপলই তালিকায় থাকে। এই নিবন্ধে নেস্টেড লুপ ব্যবহার করে solchen জোড়ার সংখ্যা গুনার পদ্ধতি দেখানো হয়েছে।

উদাহরণ কোড

my_list = [(45, 67), (11, 23), (67, 45), (23, 11), (0, 9), (67, 45)]
print("The list is :")
print(my_list)

my_result = 0
for idx in range(0, len(my_list)):
    for iidx in range(idx + 1, len(my_list)):
        # চেক করা হচ্ছে: my_list[iidx][0] == my_list[idx][1] AND my_list[idx][1] == my_list[iidx][0]
        # অর্থাৎ (a,b) এবং (b,a) উভয়ই আছে
        if my_list[iidx][0] == my_list[idx][1] and my_list[idx][1] == my_list[iidx][0]:
            my_result += 1

print("The count of bidirectional pairs are :")
print(my_result)

আউটপুট

The list is : [(45, 67), (11, 23), (67, 45), (23, 11), (0, 9), (67, 45)]
The count of bidirectional pairs are : 3

ব্যাখ্যা

• তালিকায় ৬টি টাপল আছে।

• বাইডায়রেকশনাল জোড়াগুলো:

  1. (45, 67) (ইনডেক্স ০) এবং (67, 45) (ইনডেক্স ২) → ১ জোড়া
  2. (11, 23) (ইনডেক্স ১) এবং (23, 11) (ইনডেক্স ৩) → ১ জোড়া
  3. (45, 67) (ইনডেক্স ০) এবং (67, 45) (ইনডেক্স ৫) → ১ জোড়া (ডুপ্লিকেট (67, 45) কারণে)

• মোট ৩টি জোড়া। নেস্টেড লুপ idx < iidx নিশ্চিত করে যাতে একই জোড়া দুবার গুনা না হয়।

কমপ্লেক্সিটি ও উন্নতি

• বর্তমান কমপ্লেক্সিটি O(n²)। বড় তালিকার জন্য ধীর।

• উন্নত পদ্ধতি: সেট (set) বা ডিকশনারি ব্যবহার করে O(n) এ সমাধান করা যায়।

O(n) সমাধান

from collections import Counter

pair_counts = Counter(my_list)
count = 0
for (a, b), freq in pair_counts.items():
    if a == b:
        # (x, x) টাইপ জোড়া: nC2 = n*(n-1)/2
        count += freq * (freq - 1) // 2
    elif a < b:  # ডাবল কাউন্ট এড়াতে শুধু একদিক থেকে
        rev_freq = pair_counts.get((b, a), 0)
        count += freq * rev_freq

print(count)  # 3