टीएल;डीआर

  • समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
  • दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.७: हर अक्षर अलग हो तो स्ट्रिंग के सभी क्रमचय छापो। प्रयुक्त-अक्षर झंडे वाला बैकट्रैकिंग, सादा जावा, और एबीसी का छोटा चलन।
  • जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक छोटी शब्द है। हर अक्षर अलग है। उन अक्षरों को कितने तरीकों से फिर से सजा सकते हो, और बिना दोहराए हर व्यवस्था कैसे छापोगे? यही है बिना डुप्लिकेट के क्रमचय: अलग-अलग अक्षरों वाली स्ट्रिंग के सभी क्रम बनाना।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली "सभी क्रमचय बनाओ" परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। पुनरावृत्ति और गतिशील प्रोग्रामिंग, समस्या ८.७।

१. रोज़मर्रा की उपमा

मेज़ पर तीन अलग नाम-पट्टियाँ सोचो: A, B, C। तुम हर संभव कतार चाहते हो जिसमें ये पट्टियाँ लगे लोग हों।

  • पहले आसन पर तीनों में से कोई भी चुन सकते हो।
  • दूसरे आसन पर जो पट्टियाँ अभी मेज़ पर बची हों उनमें से कोई।
  • आखिरी आसन पर जो बचे वही।

अगर इसे पेड़ की तरह खींचो तो पहले स्तर पर तीन शाखाएँ, हर दूसरे स्तर पर दो, और पत्ते पूरी कतारें: ABC, ACB, BAC, BCA, CAB, CBA। छह पत्ते, यानी 3! = 6।

कोड की चाल वही पेड़-घूमना है: चुनो, पुनरावृत्ति करो, चुनाव वापस लो ताकि अगली शाखा साफ़ मेज़ देखे। यही वापस लेना बैकट्रैकिंग है।

२. समस्या सादे शब्दों में

इनपुट: स्ट्रिंग s जिसके अक्षर सभी अलग हों (दोहरा अक्षर नहीं)।

आउटपुट: s के हर अलग क्रमचय की सूची। सूची का क्रम मायने नहीं रखता जब तक साक्षात्कारकर्ता क्रमबद्ध आउटपुट न माँगे।

उदाहरण:

इनपुट आउटपुट (कोई भी क्रम)
"abc" "abc", "acb", "bac", "bca", "cab", "cba"
"ab" "ab", "ba"
"a" "a"
"" एक खाली स्ट्रिंग (या खाली सूची; एक चुनो और उसी पर टिके रहो)

कोड से पहले स्पष्ट करो:

  • अक्षर अनोखे? (८.७ में हाँ। ८.८ डुप्लिकेट सँभालता है।)
  • केस संवेदनशील? (अगर दोनों आएँ तो 'A' और 'a' अलग।)
  • List<String> लौटाना या छापना? (सूची लौटाना जाँच में आसान।)
  • खाली स्ट्रिंग? (एक खाली क्रमचय साफ़ आधार-मामला है।)
  • इनपुट बदलना? (कॉलर की स्ट्रिंग बचाने के लिए चार ऐरे या बिल्डर बेहतर।)

३. पहले सोचो

पहले गिनती

n अनोखे अक्षरों के लिए n! क्रमचय होते हैं। n = 10 पर पहले ही तीस लाख से ऊपर। साक्षात्कार जेनरेटर चाहता है, विशाल n मुफ़्त में भरने का दावा नहीं।

कच्चा विचार (नाम लो, कोड मत लिखो)

नेस्टेड लूप या Collections.shuffle से हर क्रम बनाते रहो जब तक "काफ़ी" न लगें। यह बढ़ता नहीं, और शफ़ल पूर्णता साबित नहीं करता। फैक्टोरियल वृद्धि नाम लेने के बाद छोड़ दो।

साफ़ पुनरावृत्ति विचार

आंशिक उत्तर prefix बनाओ। हर कदम पर:

१. अगर prefix की लंबाई n है तो prefix की प्रतिलिपि रखो और लौटो। २. हर अभी न प्रयुक्त अक्षर के लिए उसे जोड़ो, पुनरावृत्ति करो, फिर हटाओ (बैकट्रैक)।

मुक्त अक्षर जानने के तरीके:

  • लंबाई n का boolean[] used (मूल स्ट्रिंग का सूचकांक), या
  • बचे अक्षरों का सेट, या
  • चार ऐरे पर स्वैप (चुने हुए अक्षर को वर्तमान सूचकांक पर लाओ, प्रत्यय पर पुनरावृत्ति, फिर वापस स्वैप)।

तीनों मान्य हैं। used ऐरे ज़ोर से समझाना आसान है। स्वैप में अतिरिक्त ढाँचा कम लगता है। नीचे स्पष्टता के लिए used है, फिर छोटी स्वैप भिन्नता।

"बिना डुप्लिकेट" क्यों मायने रखता है

अगर स्ट्रिंग में दो समान अक्षर होते तो यही पेड़ दोहरी स्ट्रिंग बनाता। समस्या ८.८ उसे ठीक करती है: जब अक्षर पिछले अप्रयुक्त भाई से मेल खाए तो छोड़ दो। यहाँ हर अक्षर अनोखा है, इसलिए हर पत्ता अलग स्ट्रिंग है। कोई अतिरिक्त छोड़-तर्क नहीं।

दूसरी क्लासिक शक्ल (वैकल्पिक)

किताब-जैसी दूसरी दृष्टि: पहले अक्षर बिना वाली स्ट्रिंग के क्रमचय लो, फिर उस अक्षर को हर उप-क्रमचय के हर सूचकांक में डालो। वही गिनती, अलग पुनरावृत्ति। बढ़ते प्रिफ़िक्स वाला बैकट्रैकिंग दबाव में अक्सर तेज़ लिखा जाता है।

४. जावा समाधान

प्रयुक्त ऐरे वाला बैकट्रैकिंग

import java.util.ArrayList;
import java.util.List;

public class PermutationsWithoutDups {

    public List<String> permutations(String s) {
        List<String> result = new ArrayList<>();
        if (s == null) {
            return result;
        }
        boolean[] used = new boolean[s.length()];
        backtrack(s, new StringBuilder(), used, result);
        return result;
    }

    private void backtrack(String s, StringBuilder path,
                           boolean[] used, List<String> result) {
        if (path.length() == s.length()) {
            result.add(path.toString());
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.append(s.charAt(i));
            backtrack(s, path, used, result);
            path.deleteCharAt(path.length() - 1); // undo
            used[i] = false;                       // undo
        }
    }
}

"abc" का चलन:

१. पथ खाली। सूचकांक ० (a) आज़माओ: पथ "a"। २. "a" से b → "ab", फिर सिर्फ c → "abc" (रखो)। c वापस, b वापस। ३. "a" से c → "ac", फिर b → "acb" (रखो)। a खाली होने तक वापस। ४. b से शुरू, फिर c से। छह स्ट्रिंग सुरक्षित।

न्यूनतम उपयोग:

List<String> perms = new PermutationsWithoutDups().permutations("abc");
// size 6; contains "abc", "acb", "bac", "bca", "cab", "cba"

स्वैप आधारित भिन्नता (वही विचार)

public List<String> permutationsSwap(String s) {
    List<String> result = new ArrayList<>();
    if (s == null) {
        return result;
    }
    char[] chars = s.toCharArray();
    swapBacktrack(chars, 0, result);
    return result;
}

private void swapBacktrack(char[] chars, int index, List<String> result) {
    if (index == chars.length) {
        result.add(new String(chars));
        return;
    }
    for (int i = index; i < chars.length; i++) {
        swap(chars, index, i);
        swapBacktrack(chars, index + 1, result);
        swap(chars, index, i); // restore
    }
}

private void swap(char[] chars, int i, int j) {
    char tmp = chars[i];
    chars[i] = chars[j];
    chars[j] = tmp;
}

गहराई index पर प्रिफ़िक्स chars[0..index) तय है। प्रत्यय का हर बचा अक्षर index पर स्वैप करके आज़माओ, पुनरावृत्ति करो, फिर वापस स्वैप। वही फैक्टोरियल पेड़, बिना boolean[]।

साक्षात्कार में दोनों रूप ठीक। एक चुनो, पूरा करो, समय बचे तो दूसरा नाम लो।

५. जटिलता तालिका

टुकड़ा लागत नोट
पत्तों की संख्या लंबाई n की अनोखी इनपुट पर n!
प्रति पत्ता काम तैयार स्ट्रिंग परिणाम में नकल करने पर ओ(n)
कुल समय हर क्रमचय स्ट्रिंग बनाने पर ओ(n · n!)
पुनरावृत्ति गहराई ओ(n)
अतिरिक्त स्थान (आउटपुट छोड़) पथ + प्रयुक्त झंडे के लिए ओ(n) (स्वैप में चार ऐरे के अलावा लगभग ओ(१))
आउटपुट स्थान हर स्ट्रिंग रखने के लिए ओ(n · n!)

समय आउटपुट-संवेदी है। जो क्रमचय लौटाते हो उसे छूते हो। पूरी सूची पर ओ(n) का दावा मत करो। विशाल n पर स्ट्रीमिंग इटरेटर या "सिर्फ गिनती" माँग सकते हैं, वह अलग उत्पाद है।

६. किनारे के मामले और आम गलतियाँ

साक्षात्कारकर्ता ये छूते हैं:

  • नल इनपुट → खाली सूची (या अपवाद; बताओ कौन सा)।
  • खाली स्ट्रिंग → सूची में एक खाली स्ट्रिंग स्वाभाविक आधार-मामला।
  • एक अक्षर → आकार १ की सूची।
  • दो अक्षर → दो स्ट्रिंग; अच्छा हाथ-से चेक।
  • लंबाई ० बनाम नल → बिना कहे एक जैसा न मानो।

आम गलतियाँ:

१. वापस लेना भूलना। अगर used[i] = true छोड़ दिया या बिल्डर में अक्षर छोड़ दिया तो आगे की शाखाएँ अक्षर खोती हैं या हमेशा बढ़ती रहती हैं। २. रखते समय साझा StringBuilder बदलना। result.add से पहले हमेशा path.toString() (नई String)। ३. क्रमबद्ध इनपुट या आउटपुट मान लेना। माँगे बिना ज़रूरी नहीं। ४. दोहरे अक्षरों पर यही कोड चलाना। दोहरे क्रमचय निकलेंगे। वह ८.८ का काम है। ५. तय n के लिए नेस्टेड लूप। लंबाई बदलते ही टूटता है। ६. दिमाग में n! गिनकर ओ(n²) कहना। पहले पत्ते गिनो, फिर प्रति पत्ता लागत।

तेज़ स्व-जाँच: "ab" पर ठीक ["ab", "ba"] (क्रम मुक्त)। "abc" पर आकार 6 और कोई दोहरी स्ट्रिंग नहीं।

७. दोस्त को समझाने वाला सार

बिना डुप्लिकेट के क्रमचय, साक्षात्कार संस्करण:

१. अक्षर अनोखे हैं, इसलिए चुनाव-पेड़ का हर पूरा रास्ता अलग स्ट्रिंग है। २. उनकी संख्या n! है। ३. पथ बनाओ। हर कदम पर अप्रयुक्त अक्षर चुनो, पुनरावृत्ति करो, फिर वापस लो। ४. पथ की लंबाई n हो तो पथ की प्रतिलिपि रखो। ५. used[] + StringBuilder, या चार ऐरे पर स्वैप: वही पेड़। ६. समय ओ(n · n!), स्थान मुख्यतः आउटपुट सूची।

अगर "abc" के छह पत्ते खींच सको, चुनो-पुनरावृत्ति-वापस लूप बिना वापसी भूले लिख सको, और फैक्टोरियल आकार नाम ले सको, तो समस्या ८.७ तुम्हारी है।

श्रृंखला