Python में नाखुश दोस्तों की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास n (सम) अलग-अलग दोस्तों की वरीयताओं की सूची है। प्रत्येक व्यक्ति i के लिए, preferences[i] वरीयता के क्रम में सॉर्ट की गई दोस्तों की सूची रखता है। तो, सूची में पहले वाला दोस्त बाद वाले दोस्त से अधिक पसंदीदा है। प्रत्येक सूची में दोस्तों को 0 से n-1 तक पूर्णांकों द्वारा नंबर किया गया है। सभी दोस्तों को अलग-अलग जोड़ों में विभाजित किया गया है। जहां pairs[i] = [xi, yi] दर्शाता है कि xi, yi के साथ जोड़ा गया है और/या yi, xi के साथ जोड़ा गया है। लेकिन एक दोस्त x नाखुश है यदि x, y के साथ जोड़ा गया है और एक दोस्त u मौजूद है जो v के साथ भी जोड़ा गया है लेकिन:

• x, y पर u को प्राथमिकता देता है, और
• u, v पर x को प्राथमिकता देता है।

उदाहरण के लिए, यदि इनपुट है preferences = [[1,2,3],[3,2,0],[3,1,0],[1,2,0]], pairs = [[0,1],[2,3]], तो आउटपुट 2 होगा क्योंकि पहला दोस्त नाखुश है क्योंकि व्यक्ति 1, व्यक्ति 0 के साथ जोड़ा गया है लेकिन व्यक्ति 3 को व्यक्ति 0 पर प्राथमिकता देता है, और व्यक्ति 3, व्यक्ति 1 को व्यक्ति 2 पर प्राथमिकता देता है। और दोस्त 3 नाखुश है क्योंकि व्यक्ति 3, व्यक्ति 2 के साथ जोड़ा गया है लेकिन व्यक्ति 1 को व्यक्ति 2 पर प्राथमिकता देता है, और व्यक्ति 1, व्यक्ति 3 को व्यक्ति 0 पर प्राथमिकता देता है।

समाधान के चरण

1. graph := defaultdict(dict) (प्रारंभ में खाली एडजेसेंसी लिस्ट)
2. pairs में प्रत्येक जोड़ी (start, end) के लिए:
   • preferences[start] में प्रत्येक pref के लिए:
     • यदि pref == end:
       • लूप से बाहर निकलें
     • graph[start][pref] = 1
   • preferences[end] में प्रत्येक pref के लिए:
     • यदि pref == start:
       • लूप से बाहर निकलें
     • graph[end][pref] = 1
3. unhappy := 0
4. pairs में प्रत्येक जोड़ी (start, end) के लिए:
   • graph[start] में प्रत्येक pref के लिए:
     • यदि graph[pref].get(start):
       • unhappy += 1
       • लूप से बाहर निकलें
   • graph[end] में प्रत्येक pref के लिए:
     • यदि graph[pref].get(end):
       • unhappy += 1
       • लूप से बाहर निकलें
5. unhappy वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

from collections import defaultdict

def solve(preferences, pairs):
    graph = defaultdict(dict)
    for start, end in pairs:
        for pref in preferences[start]:
            if pref == end:
                break
            graph[start][pref] = 1
        for pref in preferences[end]:
            if pref == start:
                break
            graph[end][pref] = 1
    unhappy = 0
    for start, end in pairs:
        for pref in graph[start]:
            if graph[pref].get(start, None):
                unhappy += 1
                break
        for pref in graph[end]:
            if graph[pref].get(end, None):
                unhappy += 1
                break
    return unhappy

preferences = [[1,2,3],[3,2,0],[3,1,0],[1,2,0]]
pairs = [[0,1],[2,3]]
print(solve(preferences, pairs))

इनपुट

[[1,2,3],[3,2,0],[3,1,0],[1,2,0]], [[0,1],[2,3]]

आउटपुट

2