大小为K的整数向量组合（在C ++中实现）

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:

整数v的组合是一组K个整数,使得它们的和是v(并且顺序很重要)。例如,2个3大小的组合物是:

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:

可以在此处找到获取这些组合的简单C ++算法:

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]

我需要找到整数向量的组成。也就是说,给定矢量v =(v1,v2,v3),我需要找到他们所有的个体成分,然后创建所有可能的组合。如果C是一个矩阵,我在第一行放置v1的分区,在第二行放置v2的分区,在第三行放置v3的分区,那么C中的行f的总和给出v [f]

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

例如,如果设置K = 2,则大小为F = 2的向量(1,2)可以在以下情况下分解:

# 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).

目标是为每个可能的C应用一些函数。我怎么能用它来做C ++?我不介意使用生成器,递归或迭代算法,只要它尽职尽责(尽可能快)。

Python

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

使用递归,yield和itertools库,Python中的实现非常好

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')

1 个解决方案

#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.

我们知道如何生成整数的所有组合(请参阅问题中的代码)。为了生成表示F整数组合的所有组合的矩阵,我们只创建整数f的所有可能组合,并且每次我们找到新组合时,我们再次调用算法以找到整数f + 1的所有可能组合。每当我们在最后一个整数中找到一个合成时,我们就完成了一个有效的矩阵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;
}