整数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?我不介意使用生成器,递归或迭代算法,只要它确实起作用(尽可能快)即可。
蟒蛇
使用递归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 回答
使用递归的解决方案:
我们知道如何生成整数的所有组合(请参阅问题中的代码)。为了生成表示 F 个整数组成的所有组合的矩阵,我们只创建所有可能的整数 f 组成,并且每次找到新的组成时,我们再次调用该算法以找到整数 f 1 的所有可能组成。在最后一个整数中找到一个成分表示我们已经完成了有效的矩阵 C。