इस समस्या में, हमें दो पूर्णांक मान k और n दिए गए हैं। और हमें 1 से n तक की संख्याओं से लंबाई k के सभी अनुक्रमों को क्रमबद्ध क्रम में प्रिंट करना है।
विषय को समझने के लिए एक उदाहरण लेते हैं -
इनपुट: k = 2 ; n = 3 आउटपुट: 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
इस समस्या में, हमें ऊपर बताए अनुसार अनुक्रम प्रिंट करना है।
इस समस्या को हल करने का एक सरल तरीका अनुक्रम के पूर्णांकों को तब तक बढ़ाना है जब तक वे अधिकतम मान यानी n तक न पहुंच जाएं। निम्नलिखित समाधान का विस्तृत विवरण है।
एल्गोरिदम
1) आकार k की एक सरणी बनाएं जिसके सभी मान 1 हों यानी {1, 1, ..ktimes}। 2) चरण 3 और 4 को तब तक दोहराएं जब तक सरणी {n, n, ..., n} न बन जाए। 3) सरणी प्रिंट करें। 4) मान को इस तरह बढ़ाएं कि सरणी के तत्व अगला मान बन जाएं। उदाहरण के लिए, {1, 1, 1} बढ़कर {1, 1, 2} हो जाता है और {1, 3, 3} बढ़कर {2, 1, 1} हो जाता है। इसके लिए हमें सरणी के kवें तत्व की जांच करनी होगी, यदि यह n के बराबर है तो अपडेट करें, फिर अनुक्रम में k-1 तत्व की जांच करें और इसी तरह उसी स्थिति के लिए। उदाहरण
निम्नलिखित प्रोग्राम अवधारणा को आपके लिए और स्पष्ट कर देगा।
#include<iostream> using namespace std; void printSequence(int arr[], int size){ for(int i = 0; i < size; i++) cout<<arr[i]<<"\t"; cout<<endl; return; } int nextElement(int arr[], int k, int n){ int s = k - 1; while (arr[s] == n) s--; if (s < 0) return 0; arr[s] = arr[s] + 1; for(int i = s + 1; i < k; i++) arr[i] = 1; return 1; } void generateSequence(int n, int k){ int *arr = new int[k]; for(int i = 0; i < k; i++) arr[i] = 1; while(1){ printSequence(arr, k); if(nextElement(arr, k, n) == 0) break; } return; } int main(){ int n = 3; int k = 2; cout<<"The sequence is :\n"; generateSequence(n, k); return 0; } आउटपुट
अनुक्रम है -
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
यह विधि समझने में आसान है लेकिन इसे बेहतर और अधिक कुशल बनाया जा सकता है।
यह विधि रिकर्सन और अनुक्रम ऑफसेट (वह मान जिसके बाद अनुक्रम उलट जाएगा) की जांच के लिए एक अतिरिक्त इंडेक्स का उपयोग करती है। फ़ंक्शन को रिकर्सिव रूप से कॉल किया जाएगा और इंडेक्स तक शर्तों को अपडेट नहीं करेगा। और इंडेक्स के बाद के शर्तों के लिए फ़ंक्शन को रिकर्स करेगा।
उदाहरण
#include<iostream> using namespace std; void printSequence (int arr[], int size){ for (int i = 0; i < size; i++) cout << arr[i] << "\t"; cout << endl; return; } void generateSequence (int arr[], int n, int k, int index){ int i; if (k == 0){ printSequence (arr, index); } if (k > 0){ for (i = 1; i <= n; ++i){ arr[index] = i; generateSequence (arr, n, k - 1, index + 1); } } } int main (){ int n = 3; int k = 2; int *arr = new int[k]; cout<<"The sequence is:\n"; generateSequence (arr, n, k, 0); return 0; } आउटपुट
अनुक्रम है -
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3