सी ++ एसटीएल में सेट का उपयोग करके व्युत्क्रमों की गणना करना

इस ट्यूटोरियल में, हम C++ STL में सेट का उपयोग करके व्युत्क्रमों की गणना करने के लिए एक प्रोग्राम पर चर्चा करेंगे।

उलटा गिनती एक माप है कि सरणी को पूरी तरह से कैसे क्रमबद्ध किया जाना है। यदि सरणी पहले से ही क्रमबद्ध है, तो उलटा गिनती 0 होगी।

उदाहरण

#include<bits/stdc++.h>
using namespace std;
//returning inversion count
int get_Icount(int arr[],int n){
   multiset<int> set1;
   set1.insert(arr[0]);
   int invcount = 0; //initializing result
   multiset<int>::iterator itset1;
   for (int i=1; i<n; i++){
      set1.insert(arr[i]);
      itset1 = set1.upper_bound(arr[i]);
      invcount += distance(itset1, set1.end());
   }
   return invcount;
}
int main()
{
   int arr[] = {8, 4, 2, 1};
   int n = sizeof(arr)/sizeof(int);
   cout << "Number of inversions count are : "<< get_Icount(arr,n);
   return 0;
}

आउटपुट

Number of inversions count are : 6