सभी "अद्वितीय" एक सेट (नहीं एक Powerset) के उप-समुच्चय उत्पन्न

Question

चलो कहते हैं कि हम एक सेट S जो कुछ सबसेट शामिल करते हैं ।

हम S के सभी संभावित सबसेट कैसे प्राप्त कर सकते हैं जिसमें S के सभी अद्वितीय तत्व ठीक से एक बार होते हैं?

फ़ंक्शन के परिणाम/विधि ऐसा ही कुछ किया जाना चाहिए:

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

वहाँ किसी भी सबसे अच्छा अभ्यास या किसी भी मानक है इसे प्राप्त करने का तरीका?

मैं एक छद्म कोड, रुबी या एरलांग उदाहरण के लिए आभारी रहूंगा।

Answer 1

यह आप क्या कर रहे हैं की तरह लगता है एक सेट/सरणी के partitions के लिए खोज रहे हैं।

ऐसा करने का एक तरीका यह रिकर्सिवली है:

• एक 1 तत्व सरणी [x] ठीक एक विभाजन
• अगर एक्स के रूप एक्स = [सिर] पूंछ, एक सरणी है तो है एक्स के विभाजन पूंछ के प्रत्येक विभाजन को ले कर और प्रत्येक संभव में सिर जोड़कर उत्पन्न होते हैं। उदाहरण के लिए यदि हम [3,2,1] के विभाजन [2 [1]] [विभाजन] [2,1]] से विभाजन उत्पन्न कर रहे थे [हम] या तो [3] से [2,1] या एक अलग तत्व के रूप में जोड़ सकते हैं , जो हमें 5 विभाजन [[3,2,1] या [[2,1], [3]] देता है [1,2,3]

एक रूबी कार्यान्वयन थोड़ा दिखता है जैसे

def partitions(x) 
    if x.length == 1 
    [[x]] 
    else 
    head, tail = x[0], x[1, x.length-1] 
    partitions(tail).inject([]) do |result, tail_partition| 
     result + partitions_by_adding_element(tail_partition, head) 
    end 
    end 
end 

def partitions_by_adding_element(partition, element) 
    (0..partition.length).collect do |index_to_add_at| 
    new_partition = partition.dup 
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element] 
    new_partition 
    end 
end 

Answer 2

लालची एल्गोरिदम का उपयोग क्यों नहीं करें?

1) प्रकार सेट एस सबसेट लंबाई
2) मैं जाने का उपयोग कर उतरते: = 0
3) [मैं] समाधान
4) एस [जे] जहां j> मैं इस तरह के रूप खोजने के लिए एस जोड़ने यह तत्व है जो वर्तमान समाधान
5 में नहीं हैं के शामिल हैं) आप तत्व 4 में वर्णित तो
5.a) स्पष्ट समाधान
5.b) मैं
5.c वृद्धि) नहीं मिल रहा है, तो अगर मैं> | S | तो तोड़ने, कोई समाधान नहीं पाया; ( 5.d) गोटो 3

संपादित
हम्म, फिर से अपनी पोस्ट पढ़ सकते हैं और निष्कर्ष यह है कि आप एक Best-First search की जरूरत के लिए आते हैं। आपका प्रश्न वास्तव में एक विभाजन समस्या नहीं है क्योंकि आपको जो चाहिए वह Change-making problem के रूप में भी जाना जाता है लेकिन बाद की स्थिति में पहला समाधान सबसे अच्छा माना जाता है - आप वास्तव में सभी समाधान ढूंढना चाहते हैं और यही कारण है कि आपको सबसे अच्छा क्यों होना चाहिए - पहली खोज रणनीति दृष्टिकोण।

Answer 3

यह क्लासिक "बैकट्रैक" व्यायाम की तरह लगता है।

• # 1: अपने सेट को ईकोदर के बीच ऑर्डर करें, इसलिए बैकट्रैक दो बार समाधान नहीं देगा।
• # 2: current_set = [], set_list = []
• # 3: लूप प्रत्येक सेट के माध्यम से चलाएं जिसमें set_list में अंतिम से कम ऑर्डर चिह्न है, (या यदि सेट_लिस्ट खाली है तो सभी)। इसे set_at_hand
• # 432: अगर set_at_hand में वर्तमान_सेट
• # 4/true/1: संघ इसे वर्तमान_सेट के साथ कोई चौराहे नहीं है, तो set_list में भी जोड़ें।
• # 4/सत्य/2: current_set पूरा हो गया? सत्य: सही समाधान की सूची में set_list जोड़ें।झूठी: # 3
• # करने के लिए recurse 4/सही/3: current_set और set_list से set_at_hand हटाने
• # 5: पाश की समाप्ति
• # 6: वापसी

Answer 4

उत्पन्न सभी सबसेट

def allSubsets set 
    combs=2**set.length 
    subsets=[] 
    for i in (0..combs) do 
     subset=[] 
     0.upto(set.length-1){|j| subset<<set[j] if i&(1<<j)!=0} 
     subsets<<subset 
    end 
    subsets 
end 

Answer 5

यहाँ एक बार देख ले: https://github.com/sagivo/algorithms/blob/master/powerset.rb
यह एक सरल एल्गोरिदम है जिसे मैंने सरणी की एक पावरसेट खोजने के लिए बनाया है।