partitions/partitions.c

#define _GNU_SOURCE
#define MAX_STR_LEN 2048

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <errno.h>
#include <string.h>
#include <igraph/igraph.h>

#define max(a,b) ({                 \
        __typeof__ (a) _a = (a);    \
        __typeof__ (b) _b = (b);    \
        _a > _b ? _a : _b;          \
    })


void usage(const char *progname, FILE *os) {
    fprintf(os, "Usage: %s <TOTAL> <DENOMINATION> ...\n", progname);
}

int cmp_double(const void *a, const void *b) {
    return (*(double*)a > *(double*)b) - (*(double*)a < *(double*)b);
}

double parse_arg(const char *a) {
    char *check_ptr;
    errno = 0;
    double val = strtod(a, &check_ptr);
    int e = errno;
    if(e) {
        fprintf(stderr, "Error %s: %s\n", strerrorname_np(e), strerror(e));
        exit(1);
    }
    if(check_ptr == a) {
        fprintf(stderr, "Error: '%s' not parsed as numeric.\n", check_ptr);
        exit(1);
    }
    if(val < 0.0) {
        fprintf(stderr, "Error: Negative input detected\n");
        exit(1);
    }
    if(check_ptr[0] != '\0') {
        fprintf(stderr, "Warning: Discarding non-numeric parts '%s' of '%s'\n", check_ptr, a);
    }
    return val;
}

void partitions(char *prefix, const double total, const double *denominations, const int ndenoms) {
    if(strnlen(prefix, MAX_STR_LEN) >= MAX_STR_LEN-1) {
        printf("WARNING: string of results is too long, truncation may be occurring.\n");
    }
    if(cmp_double(&total, &denominations[0]) < 0) {
        // We assume the denominations were pre-processed into sorted & unique order, so if the total is smaller than the smallest, there is no more partitioning to do.
        printf("%s\n", prefix);
        memset(prefix, '\0', MAX_STR_LEN);
        return;
    }
    // There are two things to do: assign a multiple of the biggest denomination to the total space, and recursively calculate what smaller denominations can go in the remaining space.
    int biggest_denom = 0;
    while(cmp_double(&total, &denominations[biggest_denom]) > 0 && biggest_denom < ndenoms) {
        ++biggest_denom;
    }
    // The previous check always goes one step too far, so pull back.
    if(biggest_denom > 0) {
        --biggest_denom;
    }
    int times = (int)floor(total/denominations[biggest_denom]);
    //printf("\nProcessing total = %f, biggest denomination = %f, number of denominations = %d. Current prefix = '%s'\n", total, denominations[biggest_denom], ndenoms, prefix);
    size_t prefix_len = strnlen(prefix, MAX_STR_LEN);
    if(ndenoms == 1) {
        // If there is only one denomination available, greedily fill the available space
        for(int p = 0; p < times; ++p) {
            char buf[MAX_STR_LEN];
            memset(buf, '\0', MAX_STR_LEN);
            strfromd(buf, MAX_STR_LEN, "%f", denominations[biggest_denom]);
            if(prefix_len > 0 || p > 0) {
                strcat(prefix, " ");
            }
            strncat(prefix, buf, 32);
        }
        printf("%s\n", prefix);
        memset(prefix, '\0', MAX_STR_LEN);
    } else if(ndenoms > 1) {
        for(int p_outer = times; p_outer >= 0; --p_outer) {
            char buf_outer[MAX_STR_LEN];
            memset(buf_outer, '\0', MAX_STR_LEN);
            strncpy(buf_outer, prefix, MAX_STR_LEN);
            for(int p_inner = 0; p_inner < p_outer; ++p_inner) {
                char buf_inner[MAX_STR_LEN];
                memset(buf_inner, '\0', MAX_STR_LEN);
                strfromd(buf_inner, MAX_STR_LEN, "%f", denominations[biggest_denom]);
                if(prefix_len > 0 || p_inner > 0) {
                    strcat(buf_outer, " ");
                }
                strncat(buf_outer, buf_inner, 32);
            }
            partitions(buf_outer, total - (double)p_outer*denominations[biggest_denom], denominations, ndenoms-1);
        }
    }
}

int main(int argc, char **argv) {
    if(argc < 3) {
        usage(argv[0], stderr);
        exit(1);
    }
    double total = parse_arg(argv[1]);
    double *denominations = (double *)malloc((argc-2)*sizeof(double));
    if(denominations == NULL) {
        fprintf(stderr, "Error allocating memory for denominations\n");
        exit(1);
    }
    unsigned int argnum = 2;
    while(argnum < argc) {
        denominations[argnum-2] = parse_arg(argv[argnum]);
        ++argnum;
    }
    int ndenoms = 1;
    if(argc > 3) {
        qsort(denominations, argc-2, sizeof(double), cmp_double);
        // overwrite dups
        int d = 1;
        while(d < argc-2) {
            while(denominations[d] == denominations[d-1] && ++d < argc-2);
            if(d >= argc-2) {
                break;
            }
            ++ndenoms;
            denominations[ndenoms-1] = denominations[d];
            ++d;
        }
    }

    char prefix[MAX_STR_LEN];
    memset(prefix, '\0', MAX_STR_LEN);
    partitions(prefix, total, denominations, ndenoms);
    if(denominations != NULL) {
        free(denominations);
    }
    return 0;
}