सरणी से चुनकर क्रमपरिवर्तन बनाना

Question

मेरे पास एक 2 डी सरणी है जो विभिन्न अक्षरों को संग्रहीत करती है जो आप फ़ोन कीपैड पर जो देखते हैं उससे मेल खाते हैं।

char [][] convert = 
    { {}, 
     {'A','B','C'}, 
     {'D','E','F'},  
     {'G','H','I'}, 
     {'J','K','L'}, 
     {'M','N','O'}, 
     {'P','R','S'}, 
     {'T','U','V'}, 
     {'W','X','Y'} 
    }; 

अगर मैं एक 5 पत्र शब्द है जो 1 पत्र 2 डी सरणी के पहले 5 पंक्तियों से प्रत्येक लेता है के सभी संभव क्रमपरिवर्तन खोजना चाहते हैं, मुझे लगता है कि कैसे करना होगा? मैं रिकर्सन के बारे में सोच रहा हूं लेकिन यह सिर्फ मुझे भ्रमित कर रहा है।

इस समस्या को समझने में अधिक आसान बनाने के लिए, यहाँ एक उदाहरण है:

एक 3 पत्र शब्द ने अपना पहला पत्र पंक्ति 1, {'A','B','C'} से, अपने दूसरे पत्र पंक्ति 3, {'G','H','I'} से लेता है, और पंक्ति 6 ​​से अपने तीसरे पत्र , {'P','R','S'}। कुल 27 संभावित परिणामों में होगा: AGP AGR AGS AHP AHR AHS AIP AIR AIS BGP BGR BGS BHP BHR BHS BIP BIR BIS CGP CGR CGS CHP CHR CHS CIP CIR CIS।

Answer 1

इसे गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करके हल किया जा सकता है।

पहले दो पंक्तियां लें और सरणी में सभी तारों को गठबंधन करें। इससे आपको आकार एम * एन का परिणामस्वरूप सरणी मिल जाएगी। जहां एम पहली सरणी का आकार है और n दूसरी सरणी का आकार है। आपके मामले में यह 9 है। फिर परिणामी सरणी को पहले सरणी में असाइन करें और दूसरी सरणी में तीसरी सरणी असाइन करें। पांचवीं सरणी तक इसे दोहराएं। इससे आपको पहले पांच सरणी से सभी संभावित तार मिलेंगे।

public static String[] getAllCombinations(String array[][], int l) { 
    String a[] = array[0]; 

    String temp[]=null; 
    for(int i=1;i<l;i++) { 
     int z=0; 
     String b[] = array[i]; 
     temp = new String[a.length*b.length]; 
     for(String x:a) { 
      for(String y:b) { 
       temp[z] = ""+x+y; 
       z++; 
      } 
     } 
     a = temp; 
    } 
    System.out.println(temp.length); 
    return temp; 
} 

यह फ़ंक्शन इसे करना चाहिए।

Answer 2

यह देखने के लिए पहली बात यह है कि यदि आप 5 पंक्तियों में से प्रत्येक में से 3 वर्णों में से एक का चयन करके शब्द बना रहे हैं, तो आप कुल 3 = 243 शब्दों के साथ समाप्त हो जाएंगे। इस कार्यक्रम के बावजूद कि आप प्रोग्राम को कैसे कार्यान्वित करते हैं, इसे 243 शब्दों में से प्रत्येक को बनाना होगा।

रिकर्सन एक अच्छी कार्यान्वयन रणनीति है क्योंकि यह स्पष्ट करता है कि आप पहली पंक्ति में तीन वर्णों में से एक का चयन कर रहे हैं, और उन विकल्पों में से प्रत्येक के लिए आप दूसरी पंक्ति में तीन वर्णों में से एक का चयन करने के लिए जाते हैं , और इसी तरह।

नीचे दिए गए जावा प्रोग्राम में, makeWord का पहला संस्करण एक रिकर्सिव फ़ंक्शन है जो currentRowIndex द्वारा अनुक्रमित पंक्ति में एक वर्ण का चयन करता है और उस वर्ण को wordBuffer पर जोड़ता है। यदि यह आखिरी पंक्ति है, तो शब्द पूर्ण हो गया है और यह शब्दों की सूची में संलग्न हो जाता है। अन्यथा, फ़ंक्शन स्वयं को currentRowIndex + 1 पर काम करने के लिए कॉल करता है।

ध्यान दें कि wordBuffer की वर्तमान स्थिति रिकर्सिव कॉल के माध्यम से होती है। रिकर्सिव कॉल से लौटने के बाद ही हम wordBuffer से अंतिम चरित्र हटाते हैं।

makeWord का दूसरा संस्करण आपको पंक्ति सूचकांकों की एक सरणी पास करने देता है जो निर्दिष्ट करता है कि आप कौन सी पंक्तियों को वर्ण चुनना चाहते हैं।उदाहरण के लिए, पंक्तियों 1, 3, और 6 से पात्रों का चयन करने के लिए, आप कहेंगे:

permuter.makeWord(new int[]{ 1, 3, 6 }, 0); 

आप वर्तमान पंक्ति के बजाय main विधि है, जो अक्षरों के साथ निर्मित किया जाना एक शब्द का कारण बनता है में है कि कॉल स्थानापन्न कर सकते हैं के माध्यम से 1 से 5 पंक्तियों से:

permuter.makeWord(1, 5); 

आप makeWord तरीकों पर विशेष ध्यान दें, तो आप देखेंगे कि पहले एक recurse नहीं है जब स्ट्रिंग पूरा हो गया है, जबकि दूसरा एक एक बार और फिर recurses जल्दी लौटता है क्योंकि position == indices.length। उत्तरार्द्ध दृष्टिकोण थोड़ा कम कुशल है क्योंकि इसकी लागत एक और रिकर्सिव कॉल है, लेकिन आप पाते हैं कि यह रिकर्सन की अवधारणा को और स्पष्ट रूप से व्यक्त करता है। यह स्वाद का मामला है।

import java.util.*; 

public class PermuteCharacters { 
    char[][] rows = { 
    {}, 
    {'A','B','C'}, 
    {'D','E','F'},  
    {'G','H','I'}, 
    {'J','K','L'}, 
    {'M','N','O'}, 
    {'P','R','S'}, 
    {'T','U','V'}, 
    {'W','X','Y'} 
    }; 

    StringBuffer wordBuffer = new StringBuffer(); 
    ArrayList<String> words = new ArrayList<String>(); 

    void makeWord(int currentRowIndex, int endRowIndex) { 
    char[] row = rows[currentRowIndex]; 
    for (int i = 0; i < row.length; ++i) { 
     wordBuffer.append(row[i]); 
     if (currentRowIndex == endRowIndex) { 
     words.add(wordBuffer.toString()); 
     } else { 
     makeWord(currentRowIndex + 1, endRowIndex); 
     } 
     wordBuffer.deleteCharAt(wordBuffer.length() - 1); 
    } 
    } 

    void makeWord(int[] indices, int position) { 
    if (position == indices.length) { 
     words.add(wordBuffer.toString()); 
     return; 
    } 
    char[] row = rows[indices[position]]; 
    for (int i = 0; i < row.length; ++i) { 
     wordBuffer.append(row[i]); 
     makeWord(indices, position + 1); 
     wordBuffer.deleteCharAt(wordBuffer.length() - 1); 
    } 
    } 

    void displayWords() { 
    if (words.size() != 0) { 
     System.out.print(words.get(0)); 
     for (int i = 1; i < words.size(); ++i) { 
     System.out.print(" " + words.get(i)); 
     } 
     System.out.println(); 
    } 
    System.out.println(words.size() + " words"); 
    } 

    public static void main(String[] args) { 
    PermuteCharacters permuter = new PermuteCharacters(); 
    permuter.makeWord(1, 5); 
    permuter.displayWords(); 
    } 
} 

Answer 3

यहां एक संभावित समाधान है।

आप पहली बार दबाए जाने वाले कुंजियों के अनुक्रम को परिभाषित करते हैं। उदाहरण के लिए, यदि आप सरणी की पहली पांच पंक्तियों में से एक अक्षर लेना चाहते हैं, तो अनुक्रम (1, 2, 3, 4, 5) होगा (क्योंकि पहली पंक्ति खाली है)। यदि आप "स्टैक" वर्तनी करना चाहते हैं, तो अनुक्रम (6, 7, 1, 1, 4) होगा।

फिर आप अनुक्रम के माध्यम से लूप करते हैं। प्रत्येक चरण में, आपको अनुक्रम की इस स्थिति के अनुरूप वर्णों की सरणी मिलती है। फिर आप उन सभी शब्दों को उत्पन्न करते हैं जो अब तक सभी संयोजनों से उत्पन्न होते हैं, जो पिछले चरण के सभी शब्द वर्तमान चरण के सभी वर्णों के साथ संयुक्त होते हैं।

अंत में, अंतिम चरण का परिणाम अंतिम परिणाम है जिसमें सभी संभावित शब्द शामिल हैं।

char [][] convert = { 
    {},    // 0 
    {'A','B','C'}, // 1 
    {'D','E','F'}, // 2 
    {'G','H','I'}, // 3 
    {'J','K','L'}, // 4 
    {'M','N','O'}, // 5 
    {'P','R','S'}, // 6 
    {'T','U','V'}, // 7 
    {'W','X','Y'} // 8 
}; 

// Sequence of keys to be pressed. In this case the pressed keys are 
// [ABC], [DEF], [GHI] 
int[] sequence = new int[] {1, 2, 3}; 

// List for storing the results of each level. 
List<List<String>> results = new ArrayList<>(); 

for(int i=0; i<sequence.length; i++){ 

    // Results of this level 
    List<String> words = new ArrayList<>(); 
    results.add(words); 

    List<String> prevLevelWords; 
    if(i==0){ 
    prevLevelWords = Collections.singletonList(""); 
    } else { 
    prevLevelWords = results.get(i-1); 
    } 

    char[] thisLevelChars = convert[sequence[i]]; 

    if(thisLevelChars.length == 0){ 
    words.addAll(prevLevelWords); 
    } else { 
    for(String word : prevLevelWords){ 
     for(char ch : convert[sequence[i]]){ 
     words.add(word + ch); 
     } 
    } 
    } 
} 

List<String> finalResult = results.get(sequence.length-1); 

for(String word : finalResult) { 
    System.out.println(word); 
} 

Run it

Answer 4

इस प्रयास करें, यदि आप Java8

static Stream<String> stream(char[] chars) { 
    return new String(chars).chars().mapToObj(c -> Character.toString((char)c)); 
} 

public static void main(String[] args) { 
    char [][] convert = 
     { {}, 
      {'A','B','C'}, 
      {'D','E','F'},  
      {'G','H','I'}, 
      {'J','K','L'}, 
      {'M','N','O'}, 
      {'P','R','S'}, 
      {'T','U','V'}, 
      {'W','X','Y'} 
     }; 
    stream(convert[1]) 
     .flatMap(s -> stream(convert[2]).map(t -> s + t)) 
     .flatMap(s -> stream(convert[3]).map(t -> s + t)) 
     .flatMap(s -> stream(convert[4]).map(t -> s + t)) 
     .flatMap(s -> stream(convert[5]).map(t -> s + t)) 
     .forEach(x -> System.out.println(x)); 
} 

उपयोग कर सकते हैं तुम भी पुनरावर्ती संस्करण लिख सकें।

static Stream<String> permutation(char[][] convert, int row) { 
    return row == 1 
     ? stream(convert[1]) 
     : permutation(convert, row - 1) 
      .flatMap(s -> stream(convert[row]).map(t -> s + t)); 
} 

और इसे कॉल करें।

permutation(convert, 5) 
     .forEach(x -> System.out.println(x)); 

Answer 5

यहां आपकी रुचि के लिए जावा 8 स्ट्रीम का उपयोग करके एक वैकल्पिक समाधान है।

public class Combiner { 
    private List<String> combos = new ArrayList<>(); 

    public Stream<String> stream() { 
     return combos.stream(); 
    } 

    public void accept(char[] values) { 
     if (combos.isEmpty()) { 
      for (char value : values) { 
       combos.add(String.valueOf(value)); 
      } 
     } else { 
      Combiner other = new Combiner(); 
      other.accept(values); 
      combine(other); 
     } 
    } 

    public Combiner combine(Combiner other) { 
     combos = stream() 
       .flatMap(v1 -> other.stream().map(v2 -> v1 + v2)) 
       .collect(Collectors.toList()); 
     return this; 
    } 
} 

अनिवार्य रूप से यह एक कलेक्टर है कि धारा में प्रत्येक तत्व लेता है और मौजूदा संयोजन तत्व में वस्तुओं और के हर संयोजन के लिए एक नया संयोजन जोड़ता है।

public static void main(String[] args) { 
    char[][] vals = {{'a', 'b'}, {'c'}, {'d', 'e'}, {'f', 'g', 'h'}}; 

    Arrays.stream(vals).parallel() 
      .collect(Combiner::new, Combiner::accept, Combiner::combine) 
      .stream().forEach(System.out::println); 
} 

parallel सख्ती से आवश्यक नहीं है: यह सिर्फ दिखाने के लिए कि संयोजनों की भारी संख्या धारा प्रोसेसर में विभाजित किया जा सकता है और उसके बाद संयुक्त के लिए है

और यहाँ कुछ नमूना है कि यह कैसे उपयोग करने के लिए दिखा कोड है ।

कोड अन्य प्रकार के डेटा के लिए बहुत आसान है जिसे स्वाभाविक रूप से स्ट्रीम किया जा सकता है। दुर्भाग्यवश Arrays.stream(char[]) नहीं है, इसलिए पारंपरिक पुनरावृत्ति कोड को थोड़ा स्पष्ट बनाता है।आप IntStream और फिर Stream<Character> पर स्ट्रिंग में कनवर्ट करने जैसे कुछ बदसूरत का उपयोग कर सकते हैं, लेकिन स्पष्ट रूप से यह सरणी पर पुनरावृत्ति से बचने के लिए बहुत सारे काम है :-)