# 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


# Partition Problem using dynamic programming in C

The Partition Problem is to determine if, given a set of positive integers, there is a subset that sums to precisely half of the sum of the set. For example, given the numbers from 1 to 7, their sum is 28, half of which is 14, and the subset (2, 3, 4, 5} sums to 14, so this is a positive instance. The partition problem is NP-complete, but can be solved in pseudo-polynomial time using dynamic programming.

The algorithm works by constructing an array with entries for every number from 0 to the sum of the set, and filling in the cells that are the sum of some subset. Once complete, the solution can be read back from the middle cell of the array, which corresponds to a subset that sums to half of the total sum. At first, only the 0 cell is filled in, because it is always possible to find a subset that sums to 0 — the empty set. After that, the cells to fill in are found by simulating repeated additions of the numbers from the set to the already-filled-in cells. For example, if the cell for some number $$m$$ is already filled in, and the set contains the number $$n$$, then the cell $$m + n$$ can be filled in. When a cell is filled in, a pointer is set to point back to the number from which it has been derived so that the solution can be read back.

Below is the code in C. The function partition() takes an array of numbers, its length, and the address of a pointer to which to attach the solution array. It returns the number of elements in the solution subset if there is a partition, or 0 otherwise.

struct partition_entry {
unsigned int value;
unsigned int truth;
unsigned int count;
struct partition_entry *prev;
};
typedef struct partition_entry partition_entry;

unsigned int sum(const unsigned int *numbers, size_t len)
{
unsigned int i, total = 0;
for (i = 0; i < len; i++) {
total += numbers[i];
}
return total;
}

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

unsigned int min(unsigned int first, unsigned int second)
{
if (first < second) {
return first;
}
return second;
}

unsigned int partition(unsigned int *numbers, size_t n, unsigned int **solution)
{
unsigned int total = sum(numbers, n);
int i, j, rightmost = 0, size;
partition_entry *partitions;
if (total % 2 == 1) {
/* Total is odd */
*solution = NULL;
return 0;
}
/* Initialise array */
partitions = malloc((total + 1) * sizeof(partition_entry));
if (partitions == NULL) {
*solution = NULL;
return 0;
}
for (i = 0; i <= total; i++) {
partitions[i].value = i;
partitions[i].truth = 0;
partitions[i].count = 0;
partitions[i].prev = NULL;
}
partitions[0].truth = 1;
/* Sort the numbers */
qsort(numbers, n,
sizeof(unsigned int), (int(*)(const void *, const void *))compare_unsigned_ints);
/* Fill in the sums and build chains */
for (i = 0; i < n; i++) {
for (j = rightmost; j >= 0; j--) {
if (partitions[j].truth && !partitions[j + numbers[i]].truth) {
partitions[j + numbers[i]].truth = 1;
partitions[j + numbers[i]].count = partitions[j].count + 1;
partitions[j + numbers[i]].prev = &partitions[j];
}
}
rightmost = min(total / 2, rightmost + numbers[i]);
}
if (partitions[total / 2].truth) {
/* Success, read back the solution */
partition_entry *ptr = &partitions[total / 2];
unsigned int number = ptr->value;
size = partitions[total / 2].count;
*solution = malloc(size * sizeof(unsigned int));
if (*solution) {
for (i = 0, j = size - 1; i < size; i++, j--) {
ptr = ptr->prev;
(*solution)[j] = number - ptr->value;
number = ptr->value;
}
}
else {
size = 0;
}
}
free(partitions);
return size;
}


Here is an example that looks for a partition of the numbers from 1 to 7:

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


The output:

Partition size: 4
2 3 4 5