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

Question

整数 v 的组合是一组 K 个整数，它们的总和为 v（顺序很重要）。例如 2 的 3 尺寸组合是：

可以找到获取这些组合的简单 C++ 算法 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;
}

但我需要一些更复杂的东西：

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

例如，大小为F=2的向量(1,2)，如果我们设置K=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

目标是对每个可能的 C 应用一些函数。我怎样才能用 C++ 做到这一点？我不介意使用生成器、递归或迭代算法，只要它能正常工作（尽可能快）。

Python

Python 中的实现使用递归 yield 和 itertools 库

非常好

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

使用递归的解决方案：

我们知道如何生成整数的所有组合（参见问题中的代码）。要生成表示 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;
}

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

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

recursion

generator

combinatorics

c++11