एक निश्चित लंबाई के सभी क्रमपरिवर्तन उत्पन्न करना

Question

मान लीजिए कि हमारे पास वर्णमाला "abcdefghiklimnop" है। मैं सक्रिय रूप से पांच समूहों के समूहों में इस वर्णमाला की पुनरावृत्ति के साथ क्रमिक रूप से क्रमपरिवर्तन कैसे उत्पन्न कर सकता हूं?

मैं अब कुछ दिनों से संघर्ष कर रहा हूं। कोई प्रतिक्रिया उपयोगी होगी।

अनिवार्य रूप से यह एक ही है के रूप में: Generating all permutations of a given string

हालांकि, मैं अभी पूरी स्ट्रिंग के पांच की लंबाई में क्रमपरिवर्तन चाहते हैं। और मैं इसे समझने में सक्षम नहीं हूं।

SO "abcdefghiklimnop" की लंबाई 5 की सभी सबस्ट्रिंग्स के लिए, सबस्ट्रिंग के क्रमपरिवर्तन को ढूंढें। उदाहरण के लिए, यदि सबस्ट्रिंग abcdef था, तो मैं उसमें से सभी क्रमपरिवर्तन चाहता हूं, या अगर सबस्ट्रिंग defli था, तो मैं उस सबस्ट्रिंग के सभी क्रमिकता चाहता हूँ। नीचे दिया गया कोड मुझे स्ट्रिंग के सभी क्रमपरिवर्तन देता है लेकिन मैं स्ट्रिंग के आकार 5 के सभी सबस्ट्रिंग्स के सभी क्रमपरिवर्तनों को खोजने के लिए उपयोग करना चाहता हूं।

public static void permutation(String str) { 
    permutation("", str); 
} 
private static void permutation(String prefix, String str) { 
    int n = str.length(); 
    if (n == 0) System.out.println(prefix); 
    else { 
     for (int i = 0; i < n; i++) 
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 
    } 
} 

Answer 1

आदेश रिकर्सिवली एक स्ट्रिंग से पांच अक्षरों लेने के लिए, एक सरल एल्गोरिथ्म का पालन करें:

• पांच चरित्र परिवर्तन में एक हिस्से को अब तक में भरा है, और पहले की स्थिति मिलना चाहिए आपका विधि कि एक चरित्र की आवश्यकता है
• यदि किसी चरित्र की आवश्यकता रखने वाली पहली स्थिति पांच से ऊपर है, तो आप कर चुके हैं; संयोजन आप अब तक है कि प्रिंट, और
• लौट अन्यथा, क्रमचय में वर्तमान स्थिति में प्रत्येक चरित्र रखा, और एक पुनरावर्ती कॉल

यह एक बहुत जावा में कम है बनाने:

private static void permutation(char[] perm, int pos, String str) { 
    if (pos == perm.length) { 
     System.out.println(new String(perm)); 
    } else { 
     for (int i = 0 ; i < str.length() ; i++) { 
      perm[pos] = str.charAt(i); 
      permutation(perm, pos+1, str); 
     } 
    } 
} 

char[] perm = new char[5]; 
permutation(perm, 0, "abcdefghiklimnop"); 

01:

फोन करने वाले perm में तत्वों की संख्या बदलकर क्रमपरिवर्तन की इच्छित लंबाई को नियंत्रित करता है

Answer 2

प्रत्येक वर्णन के पहले पांच वर्णों के सेट में पांच वर्णों के सभी क्रमपरिवर्तन शामिल होंगे। उदाहरण के लिए, यदि आप एक चार चरित्र स्ट्रिंग 'एबीसीडी' के सभी दो चरित्र क्रमपरिवर्तन चाहते आप उन्हें सभी क्रमपरिवर्तन से प्राप्त कर सकते हैं: 'एबीसीडी', 'abdc', 'acbd', 'acdb' ... 'dcba'

तो अपनी विधि में उन्हें प्रिंट करने की बजाय आप यह देखने के बाद उन्हें सूची में संग्रहीत कर सकते हैं कि यह क्रमपरिवर्तन पहले से संग्रहीत है या नहीं। सूची को या तो आपके विनिर्देश के आधार पर फ़ंक्शन या स्थिर फ़ील्ड में पास किया जा सकता है।

Answer 3

यह बिट मैनिपुलेशन का उपयोग करके आसानी से किया जा सकता है।

private void getPermutation(String str, int length) 
     { 
      if(str==null) 
       return; 
      Set<String> StrList = new HashSet<String>(); 
      StringBuilder strB= new StringBuilder(); 
      for(int i = 0;i < (1 << str.length()); ++i) 
      { 
       strB.setLength(0); //clear the StringBuilder 
       if(getNumberOfOnes(i)==length){ 
        for(int j = 0;j < str.length() ;++j){ 
        if((i & (1 << j))>0){ // to check whether jth bit is set (is 1 or not) 
         strB.append(str.charAt(j)); 
        } 
       } 
       StrList.add(strB.toString()); 
       } 
      } 
      System.out.println(Arrays.toString(StrList.toArray())); 
     } 

    private int getNumberOfOnes (int n) // to count how many numbers of 1 in binary representation of n 
    { 
     int count=0; 
     while(n>0) 
     { 
     n = n&(n-1); 
      count++; 
     } 
     return count; 
    }