डीरेंजमेंट N संख्याओं का एक क्रमपरिवर्तन है जिसमें कोई संख्या अपनी मूल स्थिति पर नहीं आती। उदाहरण के लिए {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 स्थान हैं जो वह ले सकता है,
- यदि इंडेक्स i पर कोई तत्व इंडेक्स 0 पर रखा जाता है तो, arr[i] और arr[0] की अदला-बदली होती है। अब गणना के लिए n-2 तत्व हैं।
- यदि इंडेक्स i पर तत्व इंडेक्स 0 पर नहीं रखा जाता है तो n-1 तत्वों के लिए n-2 विकल्प हैं।
आरेख

इनपुट
Arr[] = { 1, 2 } आउटपुट
डीरेंजमेंट की संख्या: 1
व्याख्या: 1 और 2 की स्थितियां इंडेक्स 0 और 1 हैं। वे केवल अपनी मूल स्थितियों की अदला-बदली करके प्राप्त कर सकते हैं। {2,1}
इनपुट
Arr[] = { 1, 2, 3 } आउटपुट
डीरेंजमेंट की संख्या: 2
व्याख्या: 1,2 और 3 की स्थितियां इंडेक्स 0,1,2 हैं।
1 को इंडेक्स 1 और 2 पर रखा जा सकता है, 2 को इंडेक्स 0 और 3 पर और 3 को इंडेक्स 0 और 1 पर।
{2,3,1} और {3,1,2} 2 डीरेंजमेंट हैं।
प्रयुक्त दृष्टिकोण
- पूर्णांक Num मौजूद संख्याओं की संख्या संग्रहीत करता है।
- रिकर्सिव फ़ंक्शन derangements(int N) संख्याओं की संख्या को इनपुट के रूप में लेता है और डीरेंजमेंट की संख्या लौटाता है।
- N=0,1,2 के लिए रिटर्न स्टेटमेंट बेस केस को संभालते हैं जिनके लिए क्रमपरिवर्तन पहले से ही 1,0 और 1 के रूप में गणना किए गए हैं।
- जब N>2 हो तो derangements() को फॉर्मूला का उपयोग करके रिकर्सिव कॉल की जाती है, (N-1)* ( derangements(N-1) + derangements(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<<"डीरेंजमेंट की संख्या: "<<derangements(Numbers); } आउटपुट
डीरेंजमेंट की संख्या: 44