जावा में संख्याओं के मनमानी समूहों पर कार्टेसियन उत्पाद कैसे बनाएं?

Question

मान लीजिए कि मैं संख्या के 2 समूह हैं:

{1, 2, 3}, 
{4, 5} 

मैं एक एल्गोरिथ्म (जावा में) बनाना चाहते हैं जो कि निम्न 6 संयोजन आउटपुट:

1,4 
1,5 
2,4 
2,5 
3,4 
3,5 

एक मनमाना संख्या नहीं हो सकता है समूह और प्रत्येक समूह के भीतर सदस्यों की मनमानी संख्या। तो उपरोक्त उदाहरण में, पहले समूह वाले 2 समूह हैं जिनमें 2 सदस्य हैं और दूसरे समूह के 2 सदस्य हैं। एक अन्य उदाहरण निम्नलिखित है (3 समूहों, दूसरे और तीसरे समूह में पहली समूहों में 3 सदस्यों और 2 सदस्य):

{1, 2, 3}, 
{4, 5}, 
{6, 7} 

निम्नलिखित में से कौन 12 संयोजनों प्राप्त होते हैं:

1,4,6 
1,4,7 
1,5,6 
1,5,7 

2,4,6 
2,4,7 
2,5,6 
2,5,7 

3,4,6 
3,4,7 
3,5,6 
3,5,7 

मैं कैसे कर सकते हैं जावा में यह? मैं प्रत्यावर्तन उपयोग करने के लिए कोशिश कर रहा हूँ और मैं एक similar question पहले से ही देखा है लेकिन मैं अभी भी कम आ रहा हूँ। सहायता के लिए धन्यवाद! एक विभाजन लेने के लिए और दृष्टिकोण को जीत के लिए हो सकता है (कृपया देखें कि यह एक होमवर्क असाइनमेंट के लिए नहीं है)

Answer 1

थोड़ा ऊब मिल गया है और यह एक शॉट देने का फैसला किया। होना चाहिए कि वास्तव में आप क्या जरूरत है:

public static void main(String args[]) { 

    ArrayList<int[]> input = new ArrayList<int[]>(); 
    input.add(new int[] { 1, 2, 3 }); 
    input.add(new int[] { 4, 5 }); 
    input.add(new int[] { 6, 7 }); 

    combine(input, new int[input.size()], 0); 
} 

private static void combine(ArrayList<int[]> input, int[] current, int k) { 

    if(k == input.size()) { 
     for(int i = 0; i < k; i++) { 
      System.out.print(current[i] + " "); 
     } 
     System.out.println(); 
    } else {    
     for(int j = 0; j < input.get(k).length; j++) { 
      current[k] = input.get(k)[j]; 
      combine(input, current, k + 1); 
     }  
    } 
} 

Answer 2

एक संभव दृष्टिकोण (जरूरी नहीं सबसे कुशल)। दो समूहों के सभी क्रमपरिवर्तनों को ढूंढना अपेक्षाकृत सरल है (सबसे कमजोर तरीका सिर्फ लूप के लिए घोंसला है)। मान लीजिए कि आप एक समारोह permute बुलाया लिखते हैं और यह permute(A,B) जहां एक (जैसे {(1), (2), (3)}) और बी (जैसे {(4), (5)} संख्याओं के समूह हैं करता है और उसे रिटर्न आप एक ही समूह के रूप में एक & बी के सभी क्रमपरिवर्तन (जैसे {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5) })

तो जब आपके पास 2 के बजाय एन समूह हैं, तो सबसे आसान काम यह है कि समस्या के छोटे हिस्से को दूर करें। मान लीजिए कि आपके पास समूह ए, बी और सी हैं। उनके बारे में चिंता करने की बजाय सभी अलग-अलग , आप की तरह कुछ के रूप में यह के बारे में सोच सकते हैं:

permute(permute(A,B),C)

एक के सभी क्रमपरिवर्तन का पता लगाएं और बी पहले। एक बार जब आप यह है कि परिणाम है, सी और चार समूहों ए, बी, सी के साथ कि परिणाम के सभी क्रमपरिवर्तन मिल जाए, डी प्रकार दिखाई देंगे:

permute(permute(permute(A,B),C),D)

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

1. आप रिकर्सिवली छोटे, अधिक व्याख्या करने योग्य समस्याओं में समस्या टूट सकता है:

   जब आप प्रत्यावर्तन कर रहे हैं, वहाँ कुछ प्रमुख सवालों के जवाब देने की जरूरत है? मुझे लगता है कि ऊपर दिए गए उदाहरण साबित करते हैं कि आप कर सकते हैं।

2. आधार केस क्या है? समाधान क्या है जो रिकर्सन को रोकने और खोलने का कारण बनता है? यह आमतौर पर कुछ सचमुच सरल होना चाहिए कि आपका रिकर्सन नीचे काम कर सकता है। इस मामले में, यह शायद permute(A,{}) जैसे कुछ नीचे आता है जहां {} खाली सेट है।

3. रिकर्सिव केस क्या है?आप समस्या का एक हिस्सा कैसे तोड़ेंगे और समस्या के एक छोटे से सबसेट पर फिर से काम करेंगे? मुझे लगता है कि प्रारंभिक स्पष्टीकरण आपको संभावित रूप से ऐसा करने का एक तरीका देता है। बस एक समय में एक समूह को तोड़ दें और इसे अपने बढ़ते परिणाम के साथ अनुमति दें।

निश्चित रूप से इस समस्या का अन्य समाधान कर रहे हैं, यह सिर्फ पहला यह है कि मेरे सिर में पॉप है। चूंकि एन बड़ा और बड़ा हो जाता है, इसलिए यह एल्गोरिदम निषिद्ध रूप से धीमा हो जाएगा क्योंकि यह बहुत ही कुशल नहीं है।

तो यदि आप इस समाधान का उपयोग नहीं करते हैं, तो भी मुझे उम्मीद है कि यह आपको सही रास्ते पर ले जाएगा!

Answer 3

कैसे (ओ प्रत्यावर्तन डब्ल्यू /) निम्नलिखित छद्म कोड के बारे में

// Create the initial result filled with the first set of numbers 
List result = new List() 
For each number in the first set 
    result.add(new List(number)) 

// Iterate over the following sets to permutate over 
For each remaining set S 
    List newResult = new List() 
    For each list L in result 
    For each number N in S 
     newResult.add(copy of L with N added) 
    result = newResult 

Answer 4

आप पुस्तकालयों का उपयोग कर सकते हैं, Guava'sSets.cartesianProduct(List<Set<E>>) करता बिल्कुल के लिए आप क्या देख रहे हैं। (प्रकटीकरण: मैं अमरूद में योगदान देता हूं।)