आकार एन के एक दिए गए सरणी में आर तत्वों के सभी संभावित संयोजनों को प्रिंट करें


कठिनाई स्तर मध्यम
में अक्सर पूछा ग्रेओरेन्ज ऑक्सिजन वॉलेट
मठ

समस्या का विवरण

एक में "आर तत्वों के सभी संभावित संयोजन प्रिंट" ऐरे आकार एन की समस्या, हमने आकार एन की एक सरणी दी है। सरणी में आकार r के सभी संयोजनों का पता लगाएं।

इनपुट प्रारूप

Th पहली और केवल एक पंक्ति जिसमें पूर्णांक N होता है।

N- अलग-अलग पूर्णांकों वाले दूसरी पंक्ति।

तीसरी पंक्ति जिसमें एक पूर्णांक आर।

आउटपुट स्वरूप

किसी दिए गए सरणी के R तत्वों के सभी संभावित संयोजनों को ऐसे प्रिंट करें जिसमें हर पंक्ति बिल्कुल एक संयोजन हो।

की कमी

  • 1 <= एन <= 10
  • 1 <= [a i] <= 10 ^ 9

उदाहरण

4 
1 2 3 4
2
1 2
1 3
1 4
2 3
2 4
3 4

कलन विधि

इस पद्धति में, मुख्य विचार आकार आर के एक अस्थायी सरणी एन्स [] बनाने और परिणाम को संग्रहीत करने के लिए है।

हम एक अस्थायी सरणी 'डेटा [] बनाते हैं, जो सभी आउटपुट को एक-एक करके स्टोर करता है। यह विचार डेटा [] में पहले सूचकांक (इंडेक्स = 0) से शुरू होता है, एक-एक करके इस इंडेक्स पर फिक्स तत्वों और शेष इंडेक्सों के लिए पुनरावृत्ति करता है। इनपुट ऐरे को {1, 2, 3, 4, 5} और r 3 होने दें। हम पहले 1 को डेटा में इंडेक्स 0 पर ठीक करते हैं [फिर] शेष इंडेक्स के लिए फिर से, फिर हम इंडेक्स 2 पर 0 को ठीक करते हैं और फिर से रीयर करते हैं। अंत में, हम 3 को ठीक करते हैं और शेष अनुक्रमित के लिए पुनरावृत्ति करते हैं। जब डेटा में तत्वों की संख्या आर (एक संयोजन के आकार) के बराबर हो जाती है, तो हम डेटा [] प्रिंट करते हैं।

1. Ans [] में पहले इंडेक्स से शुरू करें, इस इंडेक्स में एक-एक फिक्स एलीमेंट्स और बाकी इंडेक्स के लिए फिर से शुरू करें।

2. अगर ans [] array फुल हो जाती है तो ans [] array प्रिंट करें।

कार्यान्वयन

सी ++ प्रोग्राम एन ए के दिए गए एरे में आर तत्वों के सभी संभावित संयोजनों को प्रिंट करने के लिए

#include<bits/stdc++.h> 
using namespace std; 

void combination(int arr[], int data[], int start, int end, int index, int r) 
{ 
  if(index == r) 
  { 
    for (int j = 0; j < r; j++) 
      cout << data[j] << " "; 
    cout << endl; 
    return; 
  } 
  for(int i = start; i <= end && end - i + 1 >= r - index; i++) 
  { 
    data[index] = arr[i]; 
    combination(arr, data, i+1, end, index+1, r); 
  } 
} 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int r;
  cin>>r;
  int data[r]; 
  combination(a,data,0,n-1,0,r);
} 

जावा प्रोग्राम आकार के एन में दिए गए आर तत्वों के सभी संभावित संयोजनों को मुद्रित करने के लिए

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static void combination(int arr[], int data[], int start, int end, int index, int r) 
    { 
            if(index == r) 
            { 
                    for(int j = 0; j < r; j++) 
                           System.out.print(data[j]+" "); 
                    System.out.println();
                    return; 
            } 
            for(int i = start; i <= end && end - i + 1 >= r - index; i++) 
            { 
                    data[index] = arr[i]; 
                    combination(arr, data, i+1, end, index+1, r); 
            } 
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int r = sr.nextInt();
        int data [] = new int[r];
        combination(a,data,0,n-1,0,r);
    }
}
5
105 21 35 10 183
3
105 21 35 
105 21 10 
105 21 183 
105 35 10 
105 35 183 
105 10 183 
21 35 10 
21 35 183 
21 10 183 
35 10 183

जटिलता विश्लेषण

समय जटिलता

O (nCr) जहाँ n दिए गए एरे का आकार है और आर उन तत्वों की संख्या है जो हम संयोजन के लिए लेते हैं।

अंतरिक्ष जटिलता

ओ (1) क्योंकि हम यहाँ पर किसी भी सहायक स्थान का उपयोग नहीं करते हैं।