एल्गोरिथ्म है कि अभी तक

Question

नहीं इस्तेमाल किया गया है पूर्णांकों का सबसे सरल संयोजन खोजने के लिए मैं 5 0 से पूर्णांकों का सबसे सरल संयोजन खोजने (जो एक है कि पूर्णांकों और उनमें कम होते है) के लिए एक एल्गोरिथ्म रहा हूँ कि है अभी तक इस्तेमाल नहीं किया गया (प्रयुक्त संयोजन एक सूची में हैं)।

आदेश फर्क पड़ता है और संयोजन एक सूची में लौट जाना चाहिए।

उदाहरण के लिए, प्रयोग किया जाता है की संख्या के साथ सूची ऐसा दिखाई दे सकता:

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

इस में मामला है, एल्गोरिथ्म, साथ {5} एक सूची प्रदान करना चाहिए के रूप में {5} संयोजन है कि सबसे कम पूर्णांकों के होते है।

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

सूची इस तरह दिखता है, तो } {0,2} {0.3} {0,5}, ...}

एल्गोरिथ्म 0 और 4 के साथ एक सूची प्रदान करना चाहिए ({0,4})।

यह जावा में इस्तेमाल किया जा रहा है के रूप में, एक जावा जवाब बेहतर है लेकिन छद्म कोड या अन्य प्रोग्रामिंग भाषाओं भी प्रयोग करने योग्य हैं।

अग्रिम धन्यवाद!

Answer 1

मुझे लगता है कि उदाहरण 2 गलत है: {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2} के लिए, {0.3} {0,5}, ...} छोटी से छोटी समाधान, 0,0 है {} नहीं {0,4}

पूरा समाधान यहाँ है:

import java.util.*; 

public class Algorithm { 

    static List<List<Integer>> getChildren(List<Integer> node){ 
     List<List<Integer>> children = new ArrayList<List<Integer>>(); 
     for(int i = 0; i < 6; i++){ 
      List<Integer> child = new ArrayList<Integer>(node); 
      child.add(i); 
      children.add(child); 
     } 
     return children; 
    } 

    static List<Integer> find(Queue<List<Integer>> queue, Set<List<Integer>> set){ 

     for(;;){ 
      List<Integer> head = queue.poll(); 
      if(!set.contains(head)){ 
       return head; 
      } else { 
       for(List<Integer> child : getChildren(head)){ 
        queue.add(child); 
       } 
      } 
     } 
    } 

    public static void main(String[] arg) { 
     Queue<List<Integer>> queue = new LinkedList<List<Integer>>(); 
     for(int i = 0; i < 6; i++){ 
      queue.add(Collections.singletonList(i)); 
     } 
     // Example {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3},{0,5},...} 
     Set<List<Integer>> task = new HashSet<List<Integer>>(); 
     task.add(Arrays.asList(0)); 
     task.add(Arrays.asList(1)); 
     task.add(Arrays.asList(2)); 
     task.add(Arrays.asList(3)); 
     task.add(Arrays.asList(4)); 
     task.add(Arrays.asList(5)); 
     task.add(Arrays.asList(0, 1)); 
     task.add(Arrays.asList(0, 2)); 
     task.add(Arrays.asList(0, 3)); 
     task.add(Arrays.asList(0, 5)); 

     System.out.println(find(queue, task)); 
    } 

} 

Answer 2

बस क्रम में प्रत्येक संयोजन की कोशिश, कम से कम के साथ शुरू, और बंद करो जब आप एक जो प्रयोग नहीं किया जाता है? तुम कोशिश है कि, यह वास्तव में बहुत स्पष्ट लगता था?

Answer 3

है कि समस्या के लिए, मैं एक तत्व (एकल नंबर या numer की टपल) स्टोर करने के लिए एक विशेष वस्तु बनाने होगा:

class Tuple { 
    String key; 
    Set<Integer> tuple; 
} 

कुंजी संख्या के contatenation होगा, का आदेश दिया। अपने उदाहरण में, कुंजी "0" "1" "2" "3" "4" "5" "01" "02" "03" "05" होगा। मूल्य -

आप एक मानचित्र tuples स्टोर करने के लिए, संघ कुंजी के साथ उपयोग कर सकते हैं।

चूंकि चाबियाँ तार्किक क्रम का सम्मान करती हैं, अगली मुफ्त ट्यूपल ढूंढना आसान है। आप बस "0" से शुरू करते हैं और कुंजी को बढ़ाते हैं (परिभाषित क्रम का उपयोग करके), मानचित्र में जांच कर यह सत्यापित करने के लिए कि क्या टुपल पहले से उपयोग किया गया है या नहीं।

इस उदाहरण में, पहले मुफ़्त टुपल में "04" कुंजी है। इस कुंजी से, जुड़े टपल बनाने में आसान है।

Answer 4

एक पूरा (भोली) समाधान:

import java.util.*; 

public class Test { 

    public static String increment(String str) { 
     if (str.isEmpty()) return "0"; 
     int i = str.length() - 1; 
     if (str.charAt(i) < '5') 
      return str.substring(0, i) + (char) (str.charAt(i) + 1); 
     return increment(str.substring(0, i)) + "0"; 
    } 


    public static String nextUnused(Set<String> used) { 
     String s = "0"; 
     while (used.contains(s)) 
      s = increment(s); 
     return s; 
    } 

    public static void main(String args[]) { 
     Set<String> used = new HashSet<String>(Arrays.asList("0", "1", "2", "3", 
       "4", "00", "01", "02", "21", "22", "154")); 
     for (int i = 0; i < 10; i++) { 
      String toUse = nextUnused(used); 
      System.out.println("Adding " + toUse); 
      used.add(toUse); 
     } 
    } 
} 

आउटपुट:

Adding 5 
Adding 03 
Adding 04 
Adding 05 
Adding 10 
Adding 11 
Adding 12 
Adding 13 
Adding 14 
Adding 15 

आप शायद यह काफ़ी वेतन वृद्धि-विधि के लिए memoization लगाने से इसकी गति बढ़ाने सकता है।

Answer 5

यदि आपके पास सूचीबद्ध सूची है, तो 2 तरीके हैं जो मैं सोच सकता हूं कि यह एक रैखिक खोज से बेहतर होगा।

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

सबसे पहले, प्रत्येक समूह के आकार 'x' को प्रत्येक समूह को कॉल करने दें। तो, 0,1,2,3,4,5 समूह 1 है, {0,0} से {5,5} समूह 2 है।

समूह 1 से शुरू करना, अंतिम स्थिति वाले सूची स्थिति की जांच करें समूह में अगर वे सब वहाँ थे। उदाहरण के लिए, List[5] == 5। यदि ऐसा होता है, तो समूह 2 पर जाएं और दोहराएं। यदि ऐसा नहीं होता है, तो उस समूह के भीतर हमेशा एक बाइनरी खोज करने के लिए आगे बढ़ें, अंततः आपको पहले लापता मूल्य मिलेगा।

---

नहीं तो आप अंततः पूरे संयोजन स्थान का उपयोग करने की उम्मीद करता है, तो, बस पूरे संयोजन अंतरिक्ष पर एक द्विआधारी खोज की जाँच करता है, तो स्थिति में मूल्य यदि पूर्ववर्ती मान सभी अस्तित्व में उम्मीद मान से मेल खाता करते हैं।