पायथन में सभी विभिन्न पाठ्यक्रमों को कवर करने के लिए न्यूनतम सेमेस्टर की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक संख्या n है, यह दर्शाता है कि 1 से n तक के लेबल वाले n विभिन्न पाठ्यक्रम हैं। हमारे पास संबंध नामक एक सरणी भी है जहां संबंध [i] में एक जोड़ी (prevCourse_i, nextCourse_i) शामिल है, जो पाठ्यक्रम prevCourse_i और पाठ्यक्रम nextCourse_i के बीच एक पूर्वापेक्षा संबंध का प्रतिनिधित्व करता है:इसलिए पाठ्यक्रम prevCourse_i को अगले पाठ्यक्रम से पहले लिया जाना है। और हमारे पास जो अंतिम पैरामीटर है वह k है। एक सेमेस्टर में, हम अधिक से अधिक k संख्या में पाठ्यक्रम ले सकते हैं, जब तक कि हम अपने द्वारा लिए जा रहे पाठ्यक्रमों के लिए पिछले सेमेस्टर में सभी पूर्वापेक्षाएँ ले चुके हैं। हमें सभी पाठ्यक्रमों में भाग लेने के लिए आवश्यक न्यूनतम सेमेस्टर की संख्या ज्ञात करनी होगी।

तो, अगर इनपुट पसंद है

तो आउटपुट 3 होगा क्योंकि पहले सेमेस्टर में हम कोर्स 1 और 2 ले सकते हैं, अब हम कोर्स 3, 4 और 5 के लिए पात्र हैं, इसलिए अगर हम दूसरे सेमेस्टर के लिए 5 और 3 या 4 में से कोई एक लेते हैं, तो हम अगले सेमेस्टर में सभी पाठ्यक्रम समाप्त कर सकते हैं। तो हमें कुल 3 सेमेस्टर चाहिए

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

लिया :=एक नया सेट
g1 :=n खाली सूचियों वाली एक सूची
g2 :=आकार n की एक नई सूची और 0 से भरें
w :=आकार n की एक नई सूची और 0 से भरें
सेमेस्टर :=0
संबंधों में प्रत्येक x के लिए, करें
- g1[x[1]-1]
  . के अंत में x[0]-1 डालें
- g2[x[0]-1]
  . के अंत में x[1]-1 डालें
वजन :=g1 में सभी मदों की लंबाई से एक नई सूची
मैं के लिए 0 से n -1 की सीमा में, करो
- g1[i] में प्रत्येक x के लिए, करें
  - w[x] :=अधिकतम w[x] और वजन[i]
जबकि लिया का आकार
- पाठ्यक्रम :=एक नई सूची
- मैं के लिए 0 से n -1 की सीमा में, करो
  - अगर g1[i] खाली है और मैं शामिल नहीं हूं, तो
    - पाठ्यक्रम के अंत में (i, w[i]) डालें
  - यदि पाठ्यक्रम का आकार> k, तो
    - पाठ्यक्रम =दूसरे पैरामीटर के आधार पर पाठ्यक्रमों को उल्टे क्रम में क्रमबद्ध करें
    - पाठ्यक्रम :=प्रथम k पाठ्यक्रमों की सूची
  - सेमेस्टर :=सेमेस्टर + 1
  - पाठ्यक्रमों में प्रत्येक x के लिए, करें
    - g2[x[0]] में प्रत्येक y के लिए, करें
      - x[0] को g1[y]
        . से हटाएं
    - g2[x[0]] :=खाली सूची
    - x[0] को लिया में डालें
वापसी सेमेस्टर

उदाहरण

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

def solve(n, relations, k):
   taken = set()
   g1 = [[] for _ in range(n)]
   g2 = [[] for _ in range(n)]
   w = [0] * n
   semester = 0
   for x in relations:
      g1[x[1]-1].append(x[0]-1)
      g2[x[0]-1].append(x[1]-1)

   weight = list(map(len, g1))
   for i in range(n):
      for x in g1[i]:
         w[x] = max(w[x], weight[i])


   while len(taken) < n:
      courses = []
      for i in range(n):
         if (not g1[i]) and (i not in taken):
            courses.append([i,w[i]])
      if len(courses) > k:
         courses = sorted(courses, key = lambda x:x[1],reverse=True)
         courses = courses[:k]

      semester += 1

      for x in courses:
         for y in g2[x[0]]:
            g1[y].remove(x[0])
         g2[x[0]] = []
         taken.add(x[0])
   return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))

इनपुट

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