C++ में जीनों के कुल उत्परिवर्तन समूह को खोजने का कार्यक्रम

मान लीजिए हमारे पास जीन नामक स्ट्रिंग्स की एक सूची है जहां प्रत्येक तत्व की लंबाई समान होती है और प्रत्येक तत्व में "ए", "सी", "जी" और/या "टी" वर्ण होते हैं। अब कुछ नियम हैं -

• जब दो तार s1 और s2 एक वर्ण को छोड़कर एक ही स्ट्रिंग होते हैं, तो s1 और s2 एक ही उत्परिवर्तन समूह में होते हैं।

• जब दो तार s1 और s2 एक समूह में होते हैं और s2 और s3 एक समूह में होते हैं, तो s1 और s3 एक ही समूह में होते हैं।

हमें उन उत्परिवर्तन समूहों की कुल संख्या ज्ञात करनी है जो हम उत्पन्न कर सकते हैं।

इसलिए, यदि इनपुट जीन की तरह है =["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"], तो आउटपुट 2 होगा, क्योंकि दो उत्परिवर्तन समूह हैं:["ACGT", "ACGC", "ACTT"] और ["TTTT", "TTTG"]

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

• माता-पिता नामक एक मानचित्र को परिभाषित करें

• फ़ंक्शन getPar () को परिभाषित करें, इसमें एक लगेगा,

• अगर माता-पिता [ए] एक के समान है, तो:

  • वापसी एक

• माता-पिता [ए] =गेटपार (माता-पिता [ए])

• माता-पिता को लौटाएं[ए]

• एक फ़ंक्शन को परिभाषित करें (), इसमें a, b,

  . लगेगा

• पैरा:=गेटपार (ए), पैराबी:=गेटपार (बी)

• अगर पैरा, पैराबी के बराबर नहीं है, तो:

  • माता-पिता [पैरा] :=parB

  • सही लौटें

• झूठी वापसी

• फ़ंक्शन को परिभाषित करें ठीक है (), इसमें a, b,

  . लगेगा

• सीएनटी:=0

• प्रारंभ करने के लिए मैं:=0, जब मैं <आकार का, अद्यतन (मैं 1 से बढ़ाएँ), यह करें:

  • cnt :=cnt + (1 जब a[i] b[i] के समान नहीं है, अन्यथा 0)

• सीएनटी 1 होने पर सही लौटें, अन्यथा गलत

• मुख्य विधि से निम्न कार्य करें -

• सरणी को क्रमबद्ध करें v

• v

  . से तत्वों को लेकर एक सेट को परिभाषित करें

• रिट:=वी का आकार

• v में प्रत्येक तत्व के लिए, करें

  • माता-पिता [यह]:=यह

  • v में प्रत्येक तत्व के लिए, करें

  • प्रारंभ करने के लिए j :=0, जब j <इसका आकार, अद्यतन करें (1 से j बढ़ाएँ), करें:

    • अस्थायी:=यह

    • [ए, सी, जी, टी]

      . में प्रत्येक वर्ण x के लिए

      • अगर x इसके बराबर नहीं है[j], तो:

        • अस्थायी [जे]:=एक्स

        • यदि तापमान s में मौजूद है, तो:

          • अगर एकजुट (अस्थायी, यह), तो:

    • वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map <string, string> parent;
   string getPar(string& a){
      if(parent[a] == a)
         return a;
      return parent[a] = getPar(parent[a]);
   }
   bool unite(string& a, string& b){
      string parA = getPar(a);
      string parB = getPar(b);
      if(parA != parB){
         parent[parA] = parB;
         return true;
      }
      return false;
   }
   bool ok(string &a, string& b){
      int cnt = 0;
      for(int i = 0; i < a.size(); i++){
         cnt += a[i] != b[i];
      }
      return cnt == 1;
   }
   int solve(vector<string> v) {
      sort(v.begin(), v.end());
      set <string> s(v.begin(), v.end());

      int ret = v.size();
      for(auto& it : v){
         parent[it]= it;
      }
      for(auto& it : v){
         for(int j = 0; j < it.size(); j++){
            string temp = it;
            for(char x : {'A', 'C', 'G', 'T'}){
               if(x != it[j]){
                  temp[j] = x;
                  if(s.count(temp)){
                     if(unite(temp, it)) ret--;
                  }
               }
            }
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
   Solution(ob);
   cout << ob.solve(v);
}

इनपुट

{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}

आउटपुट

2