विभाजन समस्याएं ब्रूट फोर्स एल्गोरिदम

Question

मैं ब्रूटफोर्स में नीचे विभाजन समस्या के लिए छद्म कोड करने की कोशिश कर रहा हूं।

पूर्णांक एक्स और एक पूर्णांक के (के> 1) का एक सेट। एक्स जैसे के के सबसेट्स खोजें कि प्रत्येक सबसेट में संख्याएं समान राशि के बराबर होती हैं और कोई भी सबसेट में एक तत्व सामान्य नहीं होता है, या निष्कर्ष निकाला जाता है कि कोई ऐसा सबसेट नहीं है। समस्या एनपी-पूर्ण

उदाहरण के लिए, एक्स = {2, 5, 4, 9, 1, 7, 6, 8} और के = 3 के साथ, एक संभावित समाधान होगा: {2, 5, 7} {4, 9, 1} {6, 8} उन सभी को राशि अप 14.

संपूर्ण खोज रहा आम तौर पर पता है के लिए

क्योंकि हम हर संभव समाधान खोज करने के लिए है और यदि देखना होगा लक्ष्य समान है। लेकिन चूंकि यह विभाजन समस्या है यह मुश्किल हो सकता है।

एल्गोरिथ्म जानवर बल:

Subset= X.sum/K //I had a guess this would make the parition 
For int i==1; I <subset; i++ // this would change partition if not found in the first one 
If (j=0; I<n; i++) 
    Sum == s[i] 
    If sum == target 
     Display “found” 
    Else 
    “not found” 

Answer 1

यहाँ जावास्क्रिप्ट में एक उदाहरण है कि सकारात्मक सरणी तत्वों asssumes है। एल्गोरिदम ढेर को पॉप करता है और परिणाम को आउटपुट करता है यदि यह पूर्ण भागों की गिनती की जांच करके मान्य है; अन्यथा, यह प्रत्येक सरणी तत्व को बदले में ले जाता है और स्टैक पर पैरामीटर का एक और सेट जोड़ता है, एक जहां सरणी तत्व खाली हिस्से में पहला जोड़ा होता है, और जहां इसे अभी तक भरने वाले प्रत्येक भाग में जोड़ा जाता है। (सुविधा के लिए, result एक स्ट्रिंग जहां हिस्सा सूचकांक प्रत्येक सरणी तत्व के पहले आता है के रूप में अर्जित करता है।)

var arr = [2,5,4,9,1,7,6,8] 
var k = 3; 

var n = arr.length; 
var target = arr.reduce((prev, curr) => prev + curr)/k; 
var sums = []; 
for (var i=0; i<k; i++){ 
    sums[i] = 0; 
} 

var stack = [[0,sums,0,""]]; 

while (stack[0] !== undefined){ 
    var params = stack.pop(); 

    var i = params[0]; 
    var sums = params[1]; 
    var done = params[2]; 
    var result = params[3]; 

    if (done == k){ 
    console.log(result); 
    continue; 
    } else if (i == n){ 
    continue; 
    } 

    var was_first_element = false; 

    for (var j=0; j<k; j++){ 
    if (!was_first_element && sums[j] == 0){ 
     was_first_element = true; 
     var _sums = sums.slice(); 
     _sums[j] += arr[i]; 
     stack.push([i + 1,_sums,done + (_sums[j] == target ? 1 : 0),result + j + ": " + arr[i] +", "]); 
    } else if (sums[j] != 0 && arr[i] + sums[j] < target && i < n - 1){ 
     var _sums = sums.slice(); 
     _sums[j] += arr[i]; 
     stack.push([i + 1,_sums,done,result + j + ": " + arr[i] +", "]); 
    } else if (sums[j] != 0 && arr[i] + sums[j] == target){ 
     var _sums = sums.slice(); 
     _sums[j] += arr[i]; 
     stack.push([i + 1,_sums,done + 1,result + j + ": " + arr[i] +", "]); 
    } 
    } 
} 

आउटपुट:

/* 
0: 2, 1: 5, 0: 4, 1: 9, 2: 1, 2: 7, 2: 6, 0: 8 
{2,4,8} {5,9} {1,7,6} 

0: 2, 1: 5, 0: 4, 1: 9, 0: 1, 0: 7, 2: 6, 2: 8 
{2,4,1,7} {5,9} {6,8} 

0: 2, 0: 5, 1: 4, 1: 9, 1: 1, 0: 7, 2: 6, 2: 8 
{2,5,7} {4,9,1} {6,8} 
*/ 

Answer 2

मैं @ M69 द्वारा प्रदान की टिप्पणी के साथ शुरू कर देंगे। चूंकि आप जानते हैं कि सभी तत्वों का उपयोग किया जाना चाहिए, तो आप जानते हैं कि आपके विभाजन का कुल योग पूरे सेट के कुल योग के बराबर होगा। ज्ञान में जोड़ना कि प्रत्येक विभाजन में एक ही योग है, तो आप k विभाजन के लिए निर्धारित कर सकते हैं प्रत्येक को totalSum/k की आवश्यकता होगी। यह कई सेटों का पता लगाने का एक त्वरित तरीका प्रदान करता है जिन्हें k सबसेट में विभाजित नहीं किया जा सकता है। यह कोड कुछ इस तरह दिख सकता है:

if (totalSum % k != 0) 
{ 
    /* The set can't be partitioned into k elements */ 
} 

अब कुछ विभाजन बनाने शुरू करने का समय है। मैं एक पुनरावर्ती समाधान का उपयोग करने की सलाह देते हैं। तो हम एक ऐसे फ़ंक्शन से शुरू करेंगे जो एक सरणी और योग लेता है कि उस सरणी के प्रत्येक विभाजन को माना जाता है।

check_partition(array, partitionSum) 
{ 
    /* code goes here */ 
} 

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

arraySum = sum(array); 
if (sum(array) == partitionSum) 
{ 
    return array; 
} 

अन्य आधार मामला यदि सरणी का योग विभाजन तो यह प्रयास विफल हो गया का लक्ष्य राशि से कम है। इस मामले में हम यह इंगित करने के लिए शून्य लौटते हैं कि दिया गया विभाजन काम नहीं करता है।

if (sum(array) < partitionSum) 
{ 
    return null; 
} 

अब रिकर्सिव चरण लिखने के लिए। इस चरण के लिए हम सरणी से एक तत्व चुनना चाहते हैं और लक्ष्य को पूरा करने वाले प्रत्येक विभाजन को बनाना चाहते हैं जिसमें यह संख्या शामिल है।सरणी में सबसे बड़ा तत्व ऐसा करने का सबसे अच्छा तत्व है क्योंकि इसमें सबसे कम संभव विभाजन होंगे। फिर उस सेट में प्रत्येक विभाजन के लिए हम बड़े सरणी से तत्वों को निकालना चाहते हैं और फिर उस छोटी सरणी के साथ फ़ंक्शन को फिर से चलाएं।

maxElementPartitions = buildAllMaxElementPartitions(array, partitionSum); 
foreach(partition in maxElementPartitions) 
{ 
    arrayWithoutPartition = removePartition(array, partition) 
    resultSet = check_partition(arrayWithoutPartition, partitionSum); 
    if (resultSet == null) 
    { 
     /* It failed down the chain of recursion somewhere */ 
     /* Move to the next iteration of the loop */ 
    } 
    else 
    { 
     return = resultSet + partition; 
    } 
} 
/* If the loop exits no results were found */ 
return null; 

यह पुनरावर्ती क्रिया एक सफल partiton वापस आ जाएगी, या यदि कोई भी मौजूद है यह शून्य वापस आ जाएगी।