Greedy partition in C

In a previous post, I showed a dynamic programming algorithm that gives an exact solution to the partition problem. It’s also possible to get an approximate solution using a greedy algorithm.

The algorithm is:

  1. Sort the elements of the set in decreasing order
  2. For each element in the set:
    1. If the sum of the first subset is greater, put the element in the second set
    2. Else, put it in the first set

You can see intuitively that this is going to make the sets as close as possible to having the same sum without using an exact algorithm. Below is an implementation in C. The function partition() takes an array of unsigned integers and its size, and returns an array of unsigned integers which are 0 if the corresponding element is in the first set of the partition, and 1 if it is in the second set. Note that the indices of this set correspond to the array of numbers after having been sorted.

#include <stdlib.h>

int compare_unsigned_ints_decreasing(const unsigned int *p1, const unsigned int *p2)
{
    if (*p1 > *p2) {
        return -1;
    }
    if (*p1 < *p2) {
        return 1;
    }
    return 0;
}

unsigned int *partition(unsigned int *numbers, size_t n)
{
    unsigned int i, sum0 = 0, sum1 = 0;
    unsigned int *solution = calloc(n, sizeof(unsigned int));
    if (solution == NULL) {
        return NULL;
    }
    qsort(numbers, n, sizeof(unsigned int),
            (int(*)(const void *, const void *))compare_unsigned_ints_decreasing);
    for (i = 0; i < n; i++) {
        if (sum1 < sum0) {
            solution[i] = 1;
            sum1 += numbers[i];
        }
        else {
            sum0 += numbers[i];
        }
    }
    return solution;
}

Here is an example program that partitions the set of numbers from 1 to 7:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned int numbers[] = {1, 2, 3, 4, 5, 6, 7};
    const size_t len = sizeof(numbers) / sizeof(numbers[0]);
    unsigned int i;
    unsigned int *solution = partition(numbers, len);
    printf("First set:\n");
    for (i = 0; i < len; i++) {
        if (solution[i] == 0) {
            printf("%u\n", numbers[i]);
        }
    }
    printf("Second set:\n");
    for (i = 0; i < len; i++) {
        if (solution[i] == 1) {
            printf("%u\n", numbers[i]);
        }
    }
    putchar('\n');
    free(solution);
    return 0;
}

Here is the output. In this case, the partition divides the set perfectly into two sets of sum 14, but that won’t generally be the case for this algorithm as it is an approximate one.

First set:
7
4
3
Second set:
6
5
2
1