Problemi di partizione Algoritmo della forza bruta

Question

Sto cercando di eseguire lo pseudocodice per il problema della partizione di seguito in bruteforce.

un insieme di interi X e un intero k (k> 1). Trova k sottoinsiemi di X tali che i numeri in ogni sottoinsieme sommi allo stesso ammontare e che due sottoinsiemi abbiano un elemento in comune o che non esistano tali sottosistemi k . Il problema è NP-Complete

Ad esempio, con X = {2, 5, 4, 9, 1, 7, 6, 8} e ​​k = 3, una possibile soluzione potrebbe essere: {2, 5, 7}, {4, 9, 1}, {6, 8}, perché tutti loro somma fino a 14.

per la ricerca esaustiva so che in genere avremmo dovuto cercare ogni possibile soluzione e vedere se il l'obiettivo è simile. Ma dato che questo è un problema di partizione, questo potrebbe essere complicato.

La forza bruta algoritmo:

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

Ecco un esempio in JavaScript che asssumes elementi dell'array positivi. L'algoritmo apre lo stack e genera il risultato se è valido controllando il conteggio delle parti completate; altrimenti, prende a turno ogni elemento dell'array e aggiunge un altro set di parametri allo stack, uno in cui l'elemento dell'array è la prima aggiunta a una parte vuota e uno in cui viene aggiunto a turno a ciascuna delle parti ancora riempite. (Per comodità, result decorrono una stringa in cui l'indice parte precede ogni elemento dell'array.)

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

uscita:

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

Inizierò con il commento fornito da @ M69. Dato che sai che tutti gli elementi devono essere usati, allora sai che la somma totale delle tue partizioni sarà uguale alla somma totale dell'intero set. Aggiungendo la consapevolezza che ogni partizione ha la stessa somma allora è possibile determinare per le partizioni k ciascuna avrà bisogno di avere una somma di totalSum/k. Ciò fornisce un modo rapido per rilevare molti set che non possono essere suddivisi in sottoinsiemi k. Questo codice potrebbe essere qualcosa del genere:

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

Ora è il momento di iniziare a costruire alcune partizioni. Raccomando l'uso di una soluzione ricorsiva. Quindi inizieremo con una funzione che accetta una matrice e la somma che ogni partizione di tale array dovrebbe avere.

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

Ci saranno due casi base per la nostra ricorsione. La prima è che se la matrice data ha una somma totale uguale alla somma della partizione, allora il nostro partizionamento ha successo. In questo caso restituiremo l'array.

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

L'altro caso base è se la somma dell'array è inferiore alla somma obiettivo della partizione allora questo tentativo è fallito. In questo caso, restituiamo null per indicare che la partizione data non funziona.

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

Ora scrivere il passaggio ricorsivo. Per questo passaggio vogliamo selezionare un elemento dalla matrice e costruire ogni partizione che sommi alla destinazione che include questo numero.L'elemento più grande nell'array è l'elemento migliore per farlo poiché avrà il minor numero possibile di partizioni. Quindi per ogni partizione di quel set vogliamo rimuovere gli elementi al suo interno dall'array più grande e quindi eseguire nuovamente la funzione con quell'array più piccolo.

Questa funzione ricorsiva restituirà un partizionamento riuscito, oppure se non esiste nessuno restituirà null.