Problemy z partycją Brute Force Algorithm

Question

Próbuję wykonać pseudocode dla problemu partycji poniżej w bruteforce.

zestaw liczb całkowitych X i liczba całkowita k (k> 1). Znajdź k podzestawów X takich , że liczby w każdym podzestawie sumują się do tej samej liczby i nie mają dwóch podzbiorów, które mają wspólny element, lub wyciągnij wniosek, że nie istnieją takie podzbiory k. . Problem jest NP-Complete

Na przykład, przy X = {2, 5, 4, 9, 1, 7, 6, 8} i k = 3, możliwe rozwiązanie będzie: {2, 5, 7}, {4, 9, 1}, {6, 8}, ponieważ wszystkie z nich suma do 14.

do wyczerpujących poszukiwań znam zwykle musielibyśmy szukać wszelkich możliwych rozwiązań i sprawdzić, czy cel jest podobny. Ale ponieważ jest to problem z partycją, może to być trudne.

Algorytm 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

Oto przykład w JavaScript że asssumes pozytywnych elementów macierzy. Algorytm wyskakuje na stos i wyprowadza wynik, jeśli jest ważny, sprawdzając liczbę ukończonych części; w przeciwnym razie każdy element tablicy zostanie dodany po kolei i dodaje kolejny zestaw parametrów do stosu, w którym element tablicy jest pierwszym dodatkiem do pustej części, a drugi, gdzie jest dodawany z kolei do każdej z części jeszcze wypełnionych. (Dla wygody result przypada jako ciąg gdzie indeks część poprzedza każdy element tablicy.)

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

wyjściowa:

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

Zacznę komentarzu dostarczonych przez @ M69. Ponieważ wiesz, że wszystkie elementy muszą być użyte, to wiesz, że całkowita suma twoich partycji będzie równa sumie sumy całego zestawu. Dodając do wiedzy, że każda partycja ma taką samą sumę, można określić partycje o wartości k, z których każda będzie musiała mieć sumę totalSum/k. Zapewnia to szybki sposób wykrywania wielu zestawów, których nie można podzielić na podzbiory k. Ten kod może wyglądać mniej więcej tak:

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

Czas przystąpić do budowy partycji. Polecam używanie rozwiązania rekursywnego. Tak więc zaczniemy od funkcji, która pobiera tablicę i sumę, którą powinna mieć każda partycja tej tablicy.

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

Będzie istniały dwa przypadki podstawowe dla naszej rekurencji. Po pierwsze, jeśli podana tablica ma całkowitą sumę równą sumie partycji, to nasze partycjonowanie zakończy się powodzeniem. W takim przypadku zwrócimy tablicę.

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

Drugi przypadek zasadą jest, jeżeli suma tablicy jest mniejsza niż suma docelowej partycji wówczas próba nie powiodła się. W tym przypadku zwracamy wartość null, aby wskazać, że dana partycja nie działa.

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

Teraz, aby napisać krok rekursywny. W tym kroku chcemy wybrać element z tablicy i zbudować każdą partycję, która sumuje się do celu zawierającego ten numer.Największy element w tablicy jest najlepszym elementem do tego, ponieważ będzie miał najmniejszą możliwą partycję. Następnie dla każdej partycji w tym zestawie chcemy usunąć z niej elementy z większej tablicy, a następnie ponownie uruchomić funkcję z tą mniejszą tablicą.

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; 

Ta funkcja rekursywna zwróci udaną partycję, lub jeśli żadna nie istnieje, zwróci wartość null.