डिरेंजमेंट एन नंबरों का क्रमचय है जैसे कि मूल स्थिति में कोई संख्या दिखाई नहीं देती है। उदाहरण के लिए { 1,2,3 } का एक संभावित विचलन { 2,1,3 } है। इसमें कोई तत्व अपनी मूल स्थिति में नहीं है। यहाँ लक्ष्य N संख्याओं के लिए संभावित विचलनों की गणना करना है।
हम इसे एक पुनरावर्ती समाधान का उपयोग करके करेंगे। निम्नलिखित के लिए नं. तत्वों की -
- N=0, कोई गड़बड़ी नहीं, वापसी 1
- N=1, केवल एक नंबर, वापसी 0
- N=2, स्थिति की केवल एक अदला-बदली संभव है, { 1,2 } → { 2,1 }, वापसी 1
- N=3, 2 संभावित क्रमपरिवर्तन जैसे, { 1,2,3 } → { 2,3,1 }, { 3,1,2 } गिनती 2
- N=4, 9 संभावित क्रमपरिवर्तन
- ......................
- N, (N-1)*(क्रमपरिवर्तन(N-1) + क्रमपरिवर्तन(N-2))
किसी सरणी के सभी तत्वों के लिए,
-
इंडेक्स 0 के एलिमेंट में n-1 पोजीशन होती है जो वह ले सकता है,
-
यदि इंडेक्स में कोई तत्व इंडेक्स 0 पर रखा गया है, तो एआर [i] और एआर [0] को बदल दिया जाता है। अब गणना के लिए n-2 तत्व हैं।
-
यदि इंडेक्स i पर एलिमेंट को इंडेक्स 0 पर नहीं रखा गया है तो n-1 एलिमेंट के लिए n-2 विकल्प हैं।
आरेख
इनपुट
Arr[] = { 1, 2 } आउटपुट
No. of derangements : 1
स्पष्टीकरण - 1 और 2 की स्थिति सूचकांक 0 और 1 हैं। केवल वही स्थिति प्राप्त कर सकते हैं जो मूल स्थिति की अदला-बदली कर रही है। { 2,1 }
इनपुट
Arr[] = { 1, 2, 3 } आउटपुट
No. of derangements : 2
स्पष्टीकरण − 1,2 और 3 की स्थिति इंडेक्स 0,1,2 है।
1 को इंडेक्स 1 और 2 पर रखा जा सकता है, 2 को इंडेक्स 0 और 3 पर रखा जा सकता है और 3 को इंडेक्स 0 और 1 पर रखा जा सकता है।
{ 2,3,1 } और { 3,1,2 } दो विक्षोभ हैं।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक संख्या मौजूद संख्याओं की संख्या संग्रहीत करती है।
-
रिकर्सिव फंक्शन डिरेंजमेंट (इंट एन) इनपुट के रूप में संख्याओं की गिनती लेता है और नंबर लौटाता है। अव्यवस्थाओं का।
-
एन =0,1,2 के लिए रिटर्न स्टेटमेंट मूल मामलों को संभाल रहे हैं जिनके लिए क्रमपरिवर्तन की गणना पहले से ही 1,0 और 1 के रूप में की जाती है।
-
जब N>2 तब derangements() को पुनरावर्ती कॉल सूत्र का उपयोग करके किया जाता है,
(N-1)* ( डिरेंजमेंट (N-1) + डिरेंजमेंट (N-2))।
जब बैकट्रैकिंग शुरू होती है, तो गिनती की गणना की जाती है और लौटा दी जाती है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int derangements(int N){
if (N == 0)
return 1;
if (N == 1)
return 0;
if (N == 2)
return 1;
return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}
int main(){
int Numbers=5;
cout<<"Number of Derangements :"<<derangements(Numbers);
} आउटपुट
Number of Derangements :44