Partition Probleme Brute-Force-Algorithmus

Question

Ich versuche, den Pseudocode für das Partition Problem unten in Bruteforce zu tun.

eine Menge von ganzen Zahlen X und eine ganze Zahl k (k> 1). Finden Sie k Untermengen von X wie , dass die Zahlen in jeder Teilmenge auf die gleiche Menge und keine zwei Teilmengen ein Element gemeinsam haben, oder zum Schluss, dass keine solche k-Teilmengen existieren. Das Problem ist NP-Complete

Zum Beispiel wäre mit X = {2, 5, 4, 9, 1, 7, 6, 8} und k = 3 eine mögliche Lösung: {2, 5, 7}, {4, 9, 1}, {6, 8} weil alle von ihnen Summe bis 14.

für erschöpfende Suche ich weiß, normalerweise hätten wir jede mögliche Lösung suchen und sehen, ob die Ziel ist ähnlich. Aber da dies Partitionsproblem ist, könnte dies schwierig sein.

Der Algorithmus brute force:

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

Hier ist ein Beispiel in JavaScript, die positive Feldelemente asssumes. Der Algorithmus öffnet den Stapel und gibt das Ergebnis aus, wenn er gültig ist, indem er die Anzahl der abgeschlossenen Teile überprüft; andernfalls nimmt es jedes Array-Element der Reihe nach und fügt dem Stack einen weiteren Satz von Parametern hinzu, wobei das Array-Element die erste Ergänzung zu einem leeren Teil ist und eins, wo es wiederum zu jedem der Teile hinzugefügt wird, die noch gefüllt sind. (Der Einfachheit halber zufließt result als String, wo der Teil Index jedes Array-Element vorangeht.)

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] +", "]); 
    } 
    } 
} 

Output:

/* 
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

I mit dem Kommentar zur Verfügung gestellt von @ M69 startet. Da Sie wissen, dass alle Elemente verwendet werden müssen, wissen Sie, dass die Gesamtsumme Ihrer Partitionen gleich der Gesamtsumme des gesamten Satzes ist. Wenn Sie hinzufügen, dass jede Partition dieselbe Summe hat, können Sie für k Partitionen bestimmen, dass jede eine Summe von totalSum/k haben muss. Dies bietet eine schnelle Möglichkeit, viele Mengen zu erkennen, die nicht in k Untergruppen partitioniert werden können. Dieser Code könnte wie folgt aussehen:

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

Jetzt ist es Zeit, einige Partitionen zu errichten beginnen. Ich empfehle eine rekursive Lösung. Wir beginnen also mit einer Funktion, die ein Array und die Summe, die jede Partition dieses Arrays haben soll, nimmt.

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

Es gibt zwei Basisfälle für unsere Rekursion. Die erste ist, dass, wenn das gegebene Array eine Gesamtsumme hat, die gleich der Partitionssumme ist, unsere Partitionierung erfolgreich ist. In diesem Fall werden wir das Array zurückgeben.

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

der andere Basis Fall ist, wenn die Summe des Arrays kleiner als die Summe der Zielpartition dann dieser Versuch fehlgeschlagen ist. In diesem Fall geben wir null zurück, um anzuzeigen, dass die angegebene Partition nicht funktioniert.

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

Jetzt den rekursiven Schritt schreiben. Für diesen Schritt möchten wir ein Element aus dem Array auswählen und jede Partition, die zum Ziel addiert wird, mit dieser Nummer erstellen.Das größte Element in dem Array ist das beste Element, um dies zu tun, da es die wenigsten möglichen Partitionen haben wird. Dann wollen wir für jede Partition in diesem Set die Elemente aus dem größeren Array entfernen und dann die Funktion mit diesem kleineren Array erneut ausführen.

Diese rekursive Funktion gibt eine erfolgreiche Partition zurück, oder wenn keine existiert, gibt sie null zurück.