首页 文章

大小为 K 的整数向量组成(以 C 表示)

提问于
浏览
0

整数v的组成是 K 个整数的集合,这样它们的总和为v(并且顺序很重要)。例如,2 的 3-sized 组成为:

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

可以找到一个简单的 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;
}

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

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

例如,如果设置为 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

目的是对每个可能的 C 应用一些功能。我该怎么做 C?我不介意使用生成器,递归或迭代算法,只要它确实起作用(尽可能快)即可。

蟒蛇

使用递归yielditertools库,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 回答

  • 0

    使用递归的解决方案:

    我们知道如何生成整数的所有组合(请参阅问题中的代码)。为了生成表示 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;
    }
    

相关问题