यह निर्धारित करने के लिए कि क्या दिया गया शब्द दो अन्य शब्दों के बीच आता है?

सादगी के लिए, मान लें कि मेरे पास शब्दों के दो सेट हैं, जो वर्णानुक्रम में क्रमबद्ध हैं। एक सेट "आर्डवर्र्क" से शुरू होता है और "खरबूजे" पर समाप्त होता है, और दूसरा "तरबूज" से शुरू होता है और "ज़ेबरा" पर समाप्त होता है। शब्द "खरबूजे" दोनों सेटों में दिखाई देता है।

अगर मैं इनपुट शब्द लेना चाहता था, तो "केला" कहें, यह निर्धारित करने का एक अच्छा (और कुशल) तरीका क्या होगा कि यह किस प्रकार के शब्दों से संबंधित होना चाहिए? नोट: यह एक सवाल नहीं है कि "केले" शब्द पहले से ही एक सेट में मौजूद है या नहीं, बल्कि यह निर्धारित करने के बारे में एक सवाल है कि चाहिए शब्द कौन सा सेट है।

अगर कोई एल्गोरिदम है जो कोई जानता है, तो बढ़िया। अगर वे जावा में कुछ संस्करण प्रदान कर सकते हैं, तो भी बेहतर!

संपादित करें: यह भी इंगित करना चाहिए, जबकि मेरे उदाहरण में केवल 2 सेट हैं, मैं चाहता हूं कि एल्गोरिदम एन सेट के साथ काम करे।

2
@ गारेटहॉल - नहीं, वर्णमाला क्रम के आधार पर।
जोड़ा लेखक Rsaesha, स्रोत
@birryree - हाँ, खरबूजे हमेशा अंतिम शब्द है। हालांकि, मेरे पास सादगी के लिए केवल 2 सेट हैं। मैं सेट की संख्या के लिए एक एल्गोरिदम जानना चाहता हूँ।
जोड़ा लेखक Rsaesha, स्रोत
आपके उदाहरण में, "तरबूज" (या जो भी शब्द) हमेशा पहले सेट में अंतिम आइटम है? यदि ऐसा है, तो यह देखने के लिए यह जांचना आसान है कि शब्द w पहले सेट के अंतिम आइटम (जो आपके कोड में "तरबूज" है) से पहले आता है। मान लीजिए कि क्रमबद्ध क्रम में आपका मतलब है। सामान्यीकृत, आपको बस यह सेट देखने के लिए प्रत्येक सेट की जांच करने की आवश्यकता है कि यह शब्द सेट में अंतिम आइटम से पहले आता है, और फिर यह निर्धारित करें कि यह पहले आइटम के पहले या बाद में है या नहीं। यदि यह पहले नहीं आता है, तो यह उस सेट में आता है।
जोड़ा लेखक wkl, स्रोत
क्या पर आधारित होना चाहिए? वर्ग?
जोड़ा लेखक Garrett Hall, स्रोत

6 उत्तर

मान लें कि आपके पास n सेट हैं। सॉर्ट किए गए क्रम में "विभाजन" शब्दों की एक सूची बनाएं।

फिर यह सेट बस से संबंधित है:

List partitions = Arrays.asList("melon", "strawberry");
int setIndex = -(Collections.binarySearch(partitions, "banana")) - 1;

यह काम करता है क्योंकि collections.binarySearch सम्मिलन स्थिति (-1) देता है अगर उसे सूची में कुंजी नहीं मिलती है। यदि यह विभाजन शब्दों में से किसी एक के साथ टकरा सकता है तो आपको पहले जांच करनी चाहिए कि परिणाम नकारात्मक है या नहीं।

संपादित करें

I संपादित करेंed to remove the requirement for the "book-end" values ("aardvark" and "zebra") as they actually only complicated things.

2
जोड़ा

दो सेट के लिए:

यदि शब्द आपका शब्द है (उदा। "केला" ):

int cmp = word.compareTo("melon");
if (cmp < 0) {
 //it belongs to the first set
} else if (cmp > 0) {
 //it belongs to the second set
} else {
 //the word is "melon"
}

n सेट के लिए:

Place the dividing words into an ArrayList (call it dividers) in alphabetical order:

ArrayList dividers = new ArrayList();
//... populate `dividers` ...
Collections.sort(dividers);

अब आप यह पता लगाने के लिए collections.binarySearch() का उपयोग कर सकते हैं कि यह शब्द किस सेट से संबंधित है:

int pos = Collections.binarySearch(dividers, word);
if (pos >= 0) {
 //the word is the divider between sets `pos` and `pos+1`
} else {
  int num = -(pos + 1);
 //the word belong to set number `num`
}

(यहां, सेट शून्य से गिने गए हैं।)

2
जोड़ा
ठीक है, लेकिन अगर 2 से अधिक सेट हैं तो क्या होगा? क्षमा करें, मूल प्रश्न में इसे जोड़ना भूल गए। मैंने केवल सादगी के लिए 2 सेट का उपयोग किया, लेकिन मेरे वास्तविक कार्यक्रम में कई सेट होंगे, सभी वर्णानुक्रमित क्रमबद्ध होंगे। तो उदाहरण के लिए: आर्डवर्र्क - सेब, सेब - केले, केला - अपराध, अपराध - कुत्ता, ... आदि
जोड़ा लेखक Rsaesha, स्रोत
@birryree - यदि यह सेट में अंतिम शब्द के बराबर है, तो दोनों सेट किए गए हैं, और सेट (यदि यह मौजूद है) को वापस किया जाना चाहिए।
जोड़ा लेखक Rsaesha, स्रोत
@Rsaesha - क्या होता है जब शब्द सेट में अंतिम शब्द के बराबर होता है?
जोड़ा लेखक wkl, स्रोत
String mid = firstList.get(firstList.size()-1);
assert(mid.equals(secondList.get(0)));
if(newString.compareTo(mid) < 0)//belongs in first
else//belongs in second.

जाहिर है, आपको कुछ विधि कॉल को अनुकूलित करने की आवश्यकता हो सकती है कि आप उन्हें कैसे पकड़ रहे हैं।

0
जोड़ा
    final int n = 99;//whatever

    final SortedSet[] allMySets = new SortedSet[ n ];

   //put your sets into allMySets, no particular order required.

    final String searchWord = "banana";

    int i;

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

        final SortedSet< String > ss = allMySets[i];

        if ( searchWord.compareTo( ss.first() ) >= 0 && searchWord.compareTo( ss.last() ) <= 0 ) {
            System.out.println("Word " + searchWord + " belongs to set #" + i);
            break;
        }

    }

    if ( i == allMySets.length ) {
        System.out.println("No matching set found.");
       //Maybe handle border case here...
    }
0
जोड़ा

यदि आप सूचियों को संग्रहीत करने के लिए बाइनरी ढेर का उपयोग करते हैं तो यह निर्धारित करना कि कोई शब्द कहां डालना है, ओ ( लॉग एन)

0
जोड़ा

बस पहले अक्षर की जांच करें और देखें कि यह (सेट 1 का पहला अक्षर) और (सेट 1 के अंतिम तत्व का पहला अक्षर) के बीच है या नहीं। यदि यह पहले अक्षर दोनों के बराबर है, तो दूसरे अक्षरों पर जाएं। यदि यह उस सेट में फिट नहीं है तो अगले सेट पर जाएं। यह बिगओ (एन * एम) है, जहां एन सेट की संख्या है और एम आपके इनपुट शब्द में अक्षरों की संख्या है। बहुत बुरा नहीं आईएमओ।

0
जोड़ा