सेट

Question

सेट के दिए गए आकारों के साथ सबसेट की गणना करना एन तत्वों (डुप्लिकेट की अनुमति) के साथ एक सेट सी और एन
पी = {i1, i2, .../i1 + i2 + ... = n} आकार i1, i2, के सबसेट में सी के कितने अलग अपघटन ... हैं?

उदाहरण:

C = {2 2 2 3} 

P = {2 2} 
C = {2 2} U {2 3} 

P = {1 1 2} 
C = {2} U {2} U {2 3} 
C = {2} U {3} U {2 2} 

P = {1 3} 
C = {2} U {2 2 3} 
C = {3} U {2 2 2} 

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

Answer 1

तथ्य यह है कि उनमें सड़न का आदेश कोई फर्क नहीं पड़ता कि आप इसे बहुत कठिन बना देता है। यही है, आप {2 2} U {2 3} को {2 3} U {2 2} के समान देख रहे हैं। फिर भी मेरे पास एक एल्गोरिदम है जो आपके पास से बेहतर है, लेकिन यह बहुत अच्छा नहीं है।

मुझे इसे यथार्थवादी जटिल उदाहरण के साथ शुरू करने दें। हमारा सेट A B C D E F F F F G G G G होगा। विभाजन 1 1 1 1 2 2 5 होगा।

मेरा पहला सरलीकरण डेटा संरचना [[2, 4], [5, 1]] के साथ सेट में मौजूद जानकारी का प्रतिनिधित्व करना होगा, जिसका अर्थ है कि 2 तत्व 4 बार दोहराए जाते हैं, और 5 बार-बार दोहराए जाते हैं।

मेरी दूसरी स्पष्ट जटिलता [[5, 1, 1], [2, 2, 1], [4, 1, 1] के साथ विभाजन का प्रतिनिधित्व करने के लिए होगी। पैटर्न स्पष्ट नहीं हो सकता है। प्रत्येक प्रविष्टि फॉर्म [size, count, frequency] है। तो आकार 2 के 2 विभाजनों का एक अलग उदाहरण [2, 2, 1] में बदल जाता है। हम अभी तक आवृत्ति का उपयोग नहीं कर रहे हैं, लेकिन यह एक ही आकार और सामान्यता के अलग-अलग ढेर की गणना कर रहा है।

अब हम निम्नानुसार रिकर्स करने जा रहे हैं। हम सबसे आम तत्व लेंगे, और इसका उपयोग करने के सभी तरीकों को ढूंढेंगे। इसलिए हमारे मामले में हम आकार 4 के ढेर में से एक लेते हैं, और कि हम इसे विभाजित कर सकते हैं इस प्रकार है, कोषगत क्रम में प्रत्येक शेष विभाजन रणनीति उलटफेर लगता है:

1. [4][[1, 1, 1], [2, 2, 1], [1, 4, 1]] = [[2, 2, 1], [1, 4, 1], [1, 1, 1]] छोड़कर।
2. [3, [1, 0], 0][[2, 1, 1], [1, 1, 1], [2, 1, 1], [1, 4, 1]] = [[2, 1, 2], [1, 4, 1], [1, 1, 1] छोड़कर। (ध्यान दें कि अब हम आवृत्ति का उपयोग कर रहे हैं।)
3. [3, 0, 1][[2, 1, 1], [2, 2, 1], [0, 1, 1], [1, 3, 1]] = [[2, 2, 1], [2, 1, 1], [1, 3, 1]]
4. [2, [2, 0], 0] छोड़ने [[3, 1, 1], [0, 1, 1], [2, 1, 1], [1, 4, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1]]
5. [2, [1, 1], 0] छोड़ने [[3, 1, 1], [1, 2, 1], [1, 4, 1]] = [[3, 1, 1], [1, 4, 1], [1, 2, 1]]
6. [2, [1, 0], [1]] छोड़ने छोड़ने [[3, 1, 1], [1, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1], [1, 1, 1]]
7. [2, 0, [1, 1]] छोड़ने `[[3, 1, 1], [2, 2, 1], [0 , 2, 1], [1, 2, 1]] = [[3, 1, 1], [2, 2, 1], [1, 2, 1]] 1
8. [1, [2, 1]] छोड़ने [[4, 1, 1], [0, 1, 1], [1, 1, 1], [1, 4, 1]] = [[4, 1, 1], [1, 4, 1], [1, 1, 1]]
9. [1, [2, 0], [1]][[4, 1, 1], [0, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[4, 1, 1], [2, 1, 1], [1, 3, 1]]
10. [1, [1, 0], [1, 1]] छोड़ने [[4, 1, 1], [1, 1, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[4, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 1]]
11. [1, 0, [1, 1, 1]][[4, 1, 1], [2, 2, 1], [0, 3, 1], [1, 1, 1]] = [[4, 1, 1], [2, 2, 1], [1, 1, 1]]
12. [0, [2, 2]] छोड़ने [[5, 1, 1], [0, 2, 1], [1, 4, 1]] = [[5, 1, 1], [1, 4, 1]]
13. [0, [2, 1], [1]] छोड़ने [[5, 1, 1], [0, 1, 1], [1, 1, 1], [0, 1, 1], [1, 3, 1]] = [[5, 1, 1], [1, 3, 1], [1, 1, 1]]
14. [0, [2, 0], [1, 1]] छोड़ने [[5, 1, 1], [0, 2, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1], [2, 1, 1], [1, 2, 1]]
15. [0, [1, 1], [1, 1]] छोड़नेछोड़ने छोड़ने
16. [0, [1, 0], [1, 1, 1]][[5, 1, 1], [2, 2, 1], [0, 4, 1]] = [[5, 1, 1], [2, 2, 1]]

अब उन subproblems से प्रत्येक रिकर्सिवली हल किया जा सकता छोड़ने [[5, 1, 1], [1, 1, 1], [2, 1, 1], [0, 3, 1], [1, 1, 1]] = [[5, 1, 1], [2, 1, 1], [1, 1, 2]]

[0, 0, [1, 1, 1, 1]] छोड़कर। ऐसा लगता है कि हम उन्हें सब कुछ बनाने के रास्ते पर हैं, लेकिन हम नहीं हैं, क्योंकि हम memoize पुनरावर्ती कदम हैं। यह पता चला है कि 8 तरीके के पहले दो समूह एक ही 5 बाएं ओवरों के साथ हवादार हो सकते हैं। ज्ञापन के साथ हमें उन समाधानों को बार-बार पुन: गणना करने की आवश्यकता नहीं है।

उसने कहा, हम बेहतर करेंगे। 12 तत्वों के समूह को कोई समस्या नहीं होनी चाहिए। लेकिन हम नहीं कर रहे हैं कि बहुत बेहतर है। मैं आश्चर्यचकित नहीं होगा अगर यह 30 के समूहों या विभाजन के दिलचस्प सेट के साथ तत्वों के आसपास कहीं तोड़ना शुरू कर देता है। (मैंने इसे कोड नहीं किया है। यह 30 पर ठीक हो सकता है और 50 पर टूट सकता है। मुझे नहीं पता कि यह कहां टूट जाएगा। लेकिन यह देखते हुए कि आप विभाजन के सेट पर फिर से चल रहे हैं, कुछ काफी छोटे बिंदु पर टूट जाएगा।)

Answer 2

सभी विभाजन 2 चरणों में पाए जा सकते हैं।

पहला: P से एन, P_S={P_i1, P_i2, ..., P_ip} का नया आदेश दिया गया विभाजन, जैसा कि मैं समान हूं।

P = {1, 1, 1, 1, 2, 2, 5} 
P_S = (4, 4, 5) 

विभाजन P_S के संबंध में C की {C_i1, C_i2, ..., C_ip} करें। नोट, C_ix मल्टी-सेट है जैसे C। यह सी विभाजन को अंतिम विभाजन के आकार से बहु-सेट में विभाजित कर रहा है।

दूसरा: प्रत्येक {C_i1, C_i2, ..., C_ip} के लिए और t (P में ix's की संख्या) में C_ix के विभाजन के प्रत्येक ix, x={1,2,...,p} खोजने नंबर के लिए ix तत्वों के साथ सेट। इस नंबर को N(C_ix,ix,t) पर कॉल करें।

विभाजन की कुल संख्या है:

sum by all {C_i1, C_i2, ..., C_ip} (product N(C_ix,ix,t) ix={1,2,...,p}) 

पहला भाग रिकर्सिवली काफी सरल किया जा सकता है। दूसरा अधिक जटिल है। M में भागों के बहु-सेट तत्वों के विभाजन M के तत्वों के साथ सभी आंशिक रूप से क्रमबद्ध सूची को ढूंढने जैसा ही है। आंशिक रूप से आदेश सूची प्रकार का है:

a_1_1, a_1_2, ..., a_1_k, a_2_1, a_2_2, ..., a_2_k, .... 

कहाँ a_i_x <= a_i_y अगर x < y और (a_x_1, a_x_2, ..., a_x_k) lexicographic <= (a_y_1, a_y_2, ..., a_y_k) अगर x < y। इन 2 स्थितियों के साथ N(C_ix,ix,t) से सभी विभाजन को दोबारा बनाना संभव है।

कुछ मामलों के लिए N(C_ix,ix,t) की गणना करना आसान है। बहु-सेट C_ix में विभिन्न तत्वों की संख्या के रूप में |C_ix| को परिभाषित करें।

if t = 1 than 1 
if |C_ix| = 1 than 1 
if |C_ix| = 2 than (let m=minimal number of occurrences of elements in C_ix) floor(m/2) + 1 
in general if |C_ix| = 2 than partition of m in numbers <= t.