Recursive-backtracking algorithm for solving the partitioning problem

Question

Hey, i'm looking for some help to find an algorithm which divides an array of positive numbers into k-parts so that each part has the (approximately) the same sum ... let's say we have

1,2,3,4,5,6,7,8,9 en k=3 thn the algorithm should partition it like this 1,2,3,4,5|6,7|8,9 the order of the elements cannot be changed ... Finding a greedy algorithm is easy but i'm looking for a backtracking version which always returns the optimal solution ...

Annyone got any hints ?

score 5 · Answer 1 · answered Apr 28 '11 at 22:04

What do you mean by optimal solution? I believe you mean the one that minimizes the sum of each partition distance to the optimum partition. The optimum partition would be the partition that it's elements sum is equal to the total sum divided the number of partitions.

If you don't mind about efficiency, then maybe this rough approach is good enough for you. I haven't tested the algorithm to check it's correctness, so be careful.

void FindPartitions(int[] numbers, int i, IList<int>[] partitions, int currentPartition, IList<int>[] bestSolution, ref int minDistance)
{
    if (i == numbers.Length)
    {
        int sum = numbers.Sum();
        int avg = sum / partitions.Length;
        int currentDistance = 0;
        foreach (var partition in partitions)
            currentDistance += Math.Abs(partition.Sum() - avg);
        if (currentDistance < minDistance)
        {
            minDistance = currentDistance;
            for (int j = 0; j < partitions.Length; j++)
                bestSolution[j] = new List<int>(partitions[j]);
        }
    }
    else
    {
        partitions[currentPartition].Add(numbers[i]);
        FindPartitions(numbers, i + 1, partitions, currentPartition, bestSolution, ref minDistance);
        partitions[currentPartition].RemoveAt(partitions[currentPartition].Count - 1);
        if (currentPartition < partitions.Length - 1)
            FindPartitions(numbers, i, partitions, currentPartition + 1, bestSolution, ref minDistance);
    }
}

score 5 · Accepted Answer · answered Apr 29 '11 at 01:17

Here is a solution that doesn't use any dynamic data structures such as lists. They are totally unnecessary and would in practice make the algorithm much slower than necessary.

Let K be the number of partitions here and N be the number of elements in your array.

int start[K];

void register() {
   /* calculate the error between minimum and maximum value partitions */
   /* partition boundaries are start[0], start[1], start[2], ... */
   /* if lower error than previously stored, remember the best solution */
}

void rec(int s, int k) {
  if (k == K) register();
  for (int i = s; i < N; i++) {
    start[k] = i;
    rec(i + 1, k + 1);
  }
}

/* entry */
start[0] = 0;
rec(1, 1);
/* then output the best solution found at register() */

Note: this is an O(n^K) algorithm. It is sub-exponential because this is not equivalent to the general NP-complete partitioning problem has here you are looking for contiguous segments of a linear array instead of arbitrary subsets of a given total set.

score 0 · Answer 3 · answered Jan 16 '17 at 21:35

Here is a recursive algorithm in Javascript. This function returns the totals that each worker will be assigned. Lets say the input array bookLoads is an array of positive numbers that you want to divide as fairly as possible into k-parts (let's say among k workers)

Here is a working fiddle: https://jsfiddle.net/missyalyssi/jhtk8vnc/3/

function fairWork(bookLoads, numWorkers = 0) {
    // recursive version

    // utilities
    var bestDifference = Infinity;
    var bestPartition = {};
    var initLoads = {};
    var workers = Array.from({length: numWorkers}, (val, idx) => {
      initLoads[idx] = 0;
      return idx;
    });
    var bookTotal = bookLoads.reduce((acc, curr) => {return acc + curr}, 0); 
    var average = bookTotal / bookLoads.length;

    // recursive function
    function partition(books = bookLoads, workers, loads={}) {

      // if only one worker give them all the books
      if (workers.length == 1 && books.length > 0) {
        var onlyWorker = workers[0];
        loads[onlyWorker] += books.reduce((acum, curr, idx, arr) => {
                               return acum + curr;
                             },0);
        books = [];
      }

      // base case
      if (books.length == 0) {
        var keys = Object.keys(loads);
        var total = 0;
        for (let key = 0; key < keys.length; key++) {
          // square so that difference shows 
          total += Math.pow(Math.abs(average - loads[keys[key]]), 2);
        }
        if (total < bestDifference) {
          bestDifference = total;
          bestPartition= loads;
        }
        return bestPartition;
      }

      var currBookLoad = books[0];

      // add book to curr worker 1
      var newWorker1Loads = Object.assign({}, loads);
      var worker1 = workers[0]; 
      newWorker1Loads[worker1] = newWorker1Loads[worker1] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers, newWorker1Loads)

      // give to next worker
      var newNextWorkerLoads = Object.assign({}, loads);
      var worker2 = workers[1]; 
      newNextWorkerLoads[worker2] = newNextWorkerLoads[worker2] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers.slice(1), newNextWorkerLoads)

      return bestPartition;
    }
    // function call
    return partition(bookLoads, workers, initLoads)
}
fairWork([3,1,2,3], 3)
//Result will be: Object {0: 3, 1: 3, 2: 3}
fairWork([1,2,3,4,5,6,7,8,9], 3)
//Result will be: Object {0: 15, 1: 13, 2: 17}

Recursive-backtracking algorithm for solving the partitioning problem

3 Answers3