Generate all compositions of an integer into k parts

Question

I can't figure out how to generate all compositions (http://en.wikipedia.org/wiki/Composition_%28number_theory%29) of an integer N into K parts, but only doing it one at a time. That is, I need a function that given the previous composition generated, returns the next one in the sequence. The reason is that memory is limited for my application. This would be much easier if I could use Python and its generator functionality, but I'm stuck with C++.

This is similar to Next Composition of n into k parts - does anyone have a working algorithm?

Any assistance would be greatly appreciated.

Answer 1

Preliminary remarks

First start from the observation that [1,1,...,1,n-k+1] is the first composition (in lexicographic order) of n over k parts, and [n-k+1,1,1,...,1] is the last one.

Now consider an exemple: the composition [2,4,3,1,1], here n = 11 and k=5. Which is the next one in lexicographic order? Obviously the rightmost part to be incremented is 4, because [3,1,1] is the last composition of 5 over 3 parts.

4 is at the left of 3, the rightmost part different from 1.

So turn 4 into 5, and replace [3,1,1] by [1,1,2], the first composition of the remainder (3+1+1)-1 , giving [2,5,1,1,2]

Generation program (in C)

The following C program shows how to compute such compositions on demand in lexicographic order

#include <stdio.h>
#include <stdbool.h>

bool get_first_composition(int n, int k, int composition[k])
{
    if (n < k) {
        return false;
    }
    for (int i = 0; i < k - 1; i++) {
        composition[i] = 1;
    }
    composition[k - 1] = n - k + 1;
    return true;
}

bool get_next_composition(int n, int k, int composition[k])
{
    if (composition[0] == n - k + 1)    {
        return false;
    }
    // there'a an i with composition[i] > 1, and it is not 0.
    // find the last one
    int last = k - 1;
    while (composition[last] == 1) {
        last--;
    }
    // turn    a b ...   y   z 1 1 ...   1
    //                       ^ last
    // into    a b ... (y+1) 1 1 1 ... (z-1)

    // be careful, there may be no 1's at the end

    int z = composition[last];
    composition[last - 1] += 1;
    composition[last] = 1;
    composition[k - 1] = z - 1;
    return true;
}

void display_composition(int k, int composition[k])
{
    char *separator = "[";
    for (int i = 0; i < k; i++) {
        printf("%s%d", separator, composition[i]);
        separator = ",";
    }
    printf("]\n");
}


void display_all_compositions(int n, int k)
{
    int composition[k];  // VLA. Please don't use silly values for k
    for (bool exists = get_first_composition(n, k, composition);
            exists;
            exists = get_next_composition(n, k, composition)) {
        display_composition(k, composition);
    }
}

int main()
{
    display_all_compositions(5, 3);
}

Results

[1,1,3]
[1,2,2]
[1,3,1]
[2,1,2]
[2,2,1]
[3,1,1]

Weak compositions

A similar algorithm works for weak compositions (where 0 is allowed).

bool get_first_weak_composition(int n, int k, int composition[k])
{
    if (n < k) {
        return false;
    }
    for (int i = 0; i < k - 1; i++) {
        composition[i] = 0;
    }
    composition[k - 1] = n;
    return true;
}

bool get_next_weak_composition(int n, int k, int composition[k])
{
    if (composition[0] == n)    {
        return false;
    }
    // there'a an i with composition[i] > 0, and it is not 0.
    // find the last one
    int last = k - 1;
    while (composition[last] == 0) {
        last--;
    }
    // turn    a b ...   y   z 0 0 ...   0
    //                       ^ last
    // into    a b ... (y+1) 0 0 0 ... (z-1)

    // be careful, there may be no 0's at the end

    int z = composition[last];
    composition[last - 1] += 1;
    composition[last] = 0;
    composition[k - 1] = z - 1;
    return true;
}

Results for n=5 k=3

[0,0,5]
[0,1,4]
[0,2,3]
[0,3,2]
[0,4,1]
[0,5,0]
[1,0,4]
[1,1,3]
[1,2,2]
[1,3,1]
[1,4,0]
[2,0,3]
[2,1,2]
[2,2,1]
[2,3,0]
[3,0,2]
[3,1,1]
[3,2,0]
[4,0,1]
[4,1,0]
[5,0,0]

Similar algorithms can be written for compositions of n into k parts greater than some fixed value.