सरणी में ओवरलैपिंग डेटा ढूंढना

Question

हम एक सी # एप्लिकेशन लिख रहे हैं जो अनावश्यक डेटा रिपियटर्स को हटाने में मदद करेगा। एक दोहराना केवल उस मामले में हटाया जा सकता है जब सभी अन्य दोहराने वालों द्वारा प्राप्त डेटा प्राप्त होता है। उदाहरण

एक के लिए

मैं पूर्णांक सरणियों का संग्रह है, के रूप में पहले कदम bellow समझाया गया है हम क्या जरूरत है। {1, 2, 3, 4, 5}

बी। {2, 4, 6, 7}

सी। {1, 3, 5, 8, 11, 100}

यह हजारों ऐसे सरणी हो सकते हैं। मुझे उन सरणी को ढूंढने की ज़रूरत है जिन्हें हटाया जा सकता है। एक सरणी को केवल इस मामले में हटाया जा सकता है कि इसकी सभी संख्याएं अन्य सरणी में शामिल हैं। उपर्युक्त उदाहरण में, हटाया जा सकता है क्योंकि इसकी संख्या 2 और 4 सरणी बी और संख्या 1, 3, 5 सरणी सी में हैं।

इस तरह के ऑपरेशन करने का सबसे अच्छा तरीका क्या है?

Answer 1

यह न्यूनतम संख्या में सरणी के लिए अनुकूलित समाधान छोड़ दिया गया है।

सरणी के सदस्य के लिए बहुतायत शब्दकोश बनाते हैं।

1 => 2 
2 => 2 
3 => 2 
4 => 2 
5 => 2 
6 => 1 
7 => 1 
... 

चेक सरणियों से प्रत्येक और अगर सभी सदस्यों की बहुतायत 1 से अधिक कर रहे हैं, सरणी को हटा दें और अपने शब्दकोश में प्रत्येक संख्या की गिनती कम हो: उदाहरण के लिए।

Answer 2

शेष सरणी की न्यूनतम संख्या प्राप्त करना (जैसे सरणी के एक सबसेट के विपरीत जहां कहीं और एरे हटाया जा सकता है) एनपी-हार्ड set cover problem है। हालांकि, हजारों सरणी के साथ भी, एक अच्छा मौका है कि, यदि आप जुड़े विकिपीडिया लेख में फॉर्मूलेशन के लिए एक मिश्रित पूर्णांक प्रोग्राम सॉल्वर लागू करते हैं, तो यह इष्टतम समाधान ढूंढ पाएगा।