एन सूचियों से वस्तुओं को संतुलित वितरण के साथ एक साथ जोड़ने के लिए अच्छा एल्गोरिदम?

Question

मान लीजिए कि मैं तीन निम्न सूची

A1
ए 2
ए 3

बी 1
बी 2 करते

सी 1
सी 2
सी 3
सी 4
सी 5

012,351,

मैं प्रत्येक सूची से आइटम के रूप में समान रूप से इस तरह संभव sorta के रूप में वितरित साथ, एक ही सूची में उन्हें गठबंधन करने के लिए करना चाहते हैं:

सी 1
A1
सी 2
बी 1
सी 3
ए 2
सी 4
बी 2
ए 3
सी 5

मैं मैं .NET 3.5/C# का उपयोग कर रहा हूं लेकिन मैं इसके बारे में और अधिक देखने के लिए देख रहा हूं कि विशिष्ट कोड।

संपादित करें: मुझे मूल सूचियों से तत्वों का क्रम रखने की आवश्यकता है।

Answer 1

1. अधिकांश सदस्यों के साथ सूची की एक प्रति लें। यह गंतव्य सूची होगी।

2. फिर सूची को अगले सबसे बड़े नंबर के साथ लें।

3. गंतव्य सूची की लंबाई को लंबाई से विभाजित करने के लिए छोटी लंबाई से विभाजित करें ताकि एक से अधिक का आंशिक मूल्य दिया जा सके।

4. दूसरी सूची में प्रत्येक आइटम के लिए, एक फ्लोट काउंटर बनाए रखें। पिछले चरण में गणना की गई मान जोड़ें, और गणितीय रूप से इसे निकटतम पूर्णांक में घुमाएं (मूल फ़्लोट काउंटर को बरकरार रखें)। इसे गंतव्य सूची में इस स्थिति में डालें और काउंटर को इसके लिए खाते में 1 तक बढ़ाएं। दूसरी सूची में सभी सूची सदस्यों के लिए दोहराएं।

5. सभी सूचियों के लिए चरण 2-5 दोहराएँ।

संपादित करें: इस हे (एन) होने के रूप में अच्छी तरह से करने का लाभ है, जो हमेशा अच्छा :)

Answer 2

आप केवल तीन सूचियों को एक सूची में जोड़ सकते हैं और फिर उस सूची में यूएनएसओआरटी को जोड़ सकते हैं। एक अपरिवर्तित सूची को बिना किसी प्रयास के 'समान रूप से वितरित' की आपकी आवश्यकता प्राप्त करनी चाहिए।

यहां निरर्थक का कार्यान्वयन है: http://www.vanheusden.com/unsort/।

Answer 3

मैं एक विभाजन और दृष्टिकोण जीतने के बारे में सोच रहा हूं। प्रत्येक पुनरावृत्ति जिसमें आप सभी सूचियों को तत्वों के साथ विभाजित करते हैं> आधे में आधा और रिकर्स। जब आप किसी बिंदु पर पहुंच जाते हैं जहां एक को छोड़कर सभी सूचियां एक तत्व हैं, तो आप उन्हें यादृच्छिक रूप से संयोजित कर सकते हैं, एक स्तर को पॉप अप कर सकते हैं और उस फ्रेम से हटाई गई सूचियों को यादृच्छिक रूप से जोड़ सकते हैं जहां लंबाई एक थी ... et cetera।

- filter lists into three categories 
    - lists of length 1 
    - first half of the elements of lists with > 1 elements 
    - second half of the elements of lists with > 1 elements 
- recurse on the first and second half of the lists if they have > 1 element 
    - combine results of above computation in order 
- randomly combine the list of singletons into returned list 

Answer 4

एक त्वरित सुझाव, अजगर-इश स्यूडोकोड में:

merge = list() 
lists = list(list_a, list_b, list_c) 
lists.sort_by(length, descending) 

while lists is not empty: 
    l = lists.remove_first() 
    merge.append(l.remove_first()) 
    if l is not empty: 
     next = lists.remove_first() 
     lists.append(l) 
     lists.sort_by(length, descending) 
     lists.prepend(next) 

यह तत्व कम सूचियों से अधिक समान रूप से की तुलना में वितरित करना चाहिए

निम्नलिखित की तरह कुछ मैं क्या सोच रहा हूँ है यहां अन्य सुझाव।

Answer 5

सबसे पहले है, इस सवाल का जवाब एक concete समाधान की तुलना में सोचा था की एक ट्रेन के अधिक है।

ठीक है, तो आपके पास 3 आइटम (ए 1, ए 2, ए 3) की एक सूची है, जहां आप लक्ष्य सूची के पहले 1/3 में कहीं भी ए 1 होना चाहते हैं, लक्ष्य के दूसरे 1/3 में ए 2 सूची, और ए 3 तीसरे 1/3 में। इसी प्रकार आप बी 1 को पहले 1/2, आदि में होना चाहते हैं ...

तो आप अपनी सूची 10 को सरणी के रूप में आवंटित करते हैं, फिर इस मामले में अधिकांश आइटमों के साथ सूची के साथ शुरू करें। स्पॉट की गणना करें जहां सी 1 गिरना चाहिए (1.5) निकटतम स्थान पर ड्रॉप सी 1, (इस मामले में, या तो 1 या 2), फिर गणना करें कि सी 2 गिरना चाहिए (3.5) और प्रक्रिया जारी रखें जब तक कि कोई और सीएस न हो।

फिर दूसरी सबसे अधिक वस्तुओं के साथ सूची के साथ जाएं। इस मामले में, ए गणना करें कि ए 1 कहां जाता है (1.66), तो पहले 2 कोशिश करें। यदि आप पहले ही सी 1 डाल चुके हैं, तो कोशिश करें 1. ए 2 (4.66) और ए 3 (7.66) के लिए ऐसा ही करें। अंत में, हम सूची बी बी 1 को 2.5 पर जाना चाहिए, इसलिए 2 या 3 का प्रयास करें। यदि दोनों लिया जाता है, तो 1 और 4 आज़माएं और जब तक आपको रिक्त स्थान न मिल जाए तब तक मूल रूप से आगे बढ़ते रहें। बी 2 के लिए भी ऐसा ही करें।

आप कुछ इस तरह से खत्म हो जाएगा अगर आप कम संख्या लेने:

सी 1 ए 1 सी 2 ए 2 सी 3 बी 1 सी 4 ए 3 सी 5 बी 2

या इस करता है, तो आप ऊपरी नंबर लेने:

ए 1 सी 1 बी 1 सी 2 ए 2 सी 3 ए 3 सी 4 बी 2 सी 5

यह आपकी नमूना सूचियों के लिए बहुत अच्छी तरह से काम करता प्रतीत होता है, लेकिन मुझे नहीं पता कि यह कई वस्तुओं के साथ कई सूचियों में कितना अच्छा होगा। इसे आज़माएं और मुझे बताएं कि यह कैसा चल रहा है।

Answer 6

• सूचियों की हैश तालिका बनाएं।
• प्रत्येक सूची के लिए, कुंजी (/ n (+ (length list) 1))
• वैकल्पिक अंतर्गत सूची में n वें तत्व की दुकान हैश तालिका में प्रत्येक कुंजी के अंतर्गत सूचियों शफ़ल, या किसी तरह
• जुटना में उन्हें सॉर्ट हैश में सूचियों द्वारा हल कर एंड्रयू Rollings के प्रमुख

Answer 7

कार्यान्वयन 'जवाब:

public List<String> equimix(List<List<String>> input) { 

    // sort biggest list to smallest list 
    Collections.sort(input, new Comparator<List<String>>() { 
    public int compare(List<String> a1, List<String> a2) { 
     return a2.size() - a1.size(); 
    } 
    }); 

    List<String> output = input.get(0); 

    for (int i = 1; i < input.size(); i++) { 
    output = equimix(output, input.get(i)); 
    } 

    return output; 
} 

public List<String> equimix(List<String> listA, List<String> listB) { 

    if (listB.size() > listA.size()) { 
    List<String> temp; 
    temp = listB; 
    listB = listA; 
    listA = temp; 
    } 

    List<String> output = listA; 

    double shiftCoeff = (double) listA.size()/listB.size(); 
    double floatCounter = shiftCoeff; 

    for (String item : listB) { 
    int insertionIndex = (int) Math.round(floatCounter); 
    output.add(insertionIndex, item); 
    floatCounter += (1+shiftCoeff); 
    } 

    return output; 
}