Integer vector compositions of size K (Implementation in C++)

Question

A composition of an integer v is a set of K integers such that their sum is v (and order matters). For instance the 3-sized compositions of 2 are:

2 0 0 
1 1 0 
1 0 1 
0 2 0 
0 1 1 
0 0 2 

A simple C++ algorithm to obtains these compositions can be found here:

void print(std::vector<int>& a) {
    std::ostream_iterator<int> i(std::cout, " ");
    std::copy(a.begin(), a.end(), i);
    std::cout << "\n";
}

void recurse(std::vector<int>& a, int pos, int remaining) {
    if (remaining == 0) { print(a); return; }
    if (pos == a.size()) { return; }
    for (int i = remaining; i >= 0; --i) {
        a[pos] = i;
        recurse(a, pos + 1, remaining - i);
     }
 }

int main() {
  int v = 2, k = 3;
  std::vector<int> a(k);
  recurse(a, 0, v);
  return 0;
}

But I need something a bit more complex:

I need to find the compositions of a integer vector. That is, given a vector v=(v1, v2, v3) I need to find all their individual compositions and then create all possible combinations. If C is a matrix where I put a partition of v1 in the first row, a partition of v2 in the second row, and a partition of v3 in the third row, then the sum of row f in C gives v[f]

For instance, the vector (1,2) of size F=2, if we set K=2, can be decomposed in:

# all sets of K vectors such that their sum is (1,2)
C_1 = 1,0   C_2 = 1,0  C_3 = 1,0 C_4 =  0,1   C_5 = 0,1  C_6 = 0,1
      2,0         1,1        0,2        2,0         1,1        0,2

The goal is to apply some function to each possible C. How can I do it it C++? I don't mind using generators, recursive or iterative algorithms as long as it does de job (as fast as possible).

Python

The implementation in Python is quite nice using recursions, yield, and the itertools library

import numpy as np
import itertools

# Generator to yield all K-size compositions of integer n
def findCombiR(n,K):
    if K==1:
        yield [n]
        return

    for i in range(0,n+1):
        for result in findCombiR(n-i,K-1):
            yield [i] + result

# Generator to yield all K-size compositions of a F-length vector
def findCombiR_v(v,K):
    out = []
    for f in range(0, len(v)):
        out.append(findCombiR(v[f],K))

    return out

# Main
####################

v = [1,2]
F = len(v)
K = 2

# C stores F composition generators, one for each element in v.
C = findCombiR_v(v,K)
#"product" combines all possible outputs of the F generators
for c in itertools.product(*C): 
    c = np.reshape(c, (F,K))
    print(c, '\n')

Answer 1

A solution using recursivity:

We know how to generate all compositions of an integer (see code in the question). To generate matrices that represent all combinations of compositions of F integers, we just create all possible compositions of integer f, and each time we find a new composition we call the algorithm again to find all possible compositions of the integer f+1. Each time we find a composition in the last integer means we have completed a valid matrix C.

#include <iostream>
#include <armadillo>

using namespace arma;

void recursevec(arma::ivec v, arma::imat& C, int f, int pos, int remaining) {

    // If there is no remaining left, we completed a new composition for v[f]
    if (remaining == 0) { 

        // If elements in v left, get the combinations of v[f+1]
        if(f < (C.n_rows-1)){
            recursevec(v, C, f+1, 0, v[f+1]);
            return;
        } 
        // If last f, then we are done and we completed a new C
        else {
            std::cout << C << std::endl;
            return;
        }
    }

    // If position pointer got out of the vector, 
    // then there is nothing to do
    if (pos == C.n_cols) { return; }

    // Else, continue allocating the remaining in all possible ways
    for (int i = remaining; i >= 0; --i) {
        C(f, pos) = i;
        recursevec(v, C, f, pos + 1, remaining - i);
    }
}

// Test vector compositions
int main() {
  arma::ivec v = {1,2};
  int F = v.size();
  int K = 2;
  arma::imat C(F,K);
  recursevec(v, C, 0, 0, v[0]);
  return 0;
}