高效计算矢量组合

本文介绍了高效计算矢量组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在研究的问题，出于好奇，我不知道如何编程，我已经在脑海中的逻辑。让我来解释给你听：

I'm working on a research problem out of curiosity, and I don't know how to program the logic that I've in mind. Let me explain it to you:

我有四个矢量，比方说，

I've four vectors, say for example,

v1 = 1 1 1 1 v2 = 2 2 2 2 v3 = 3 3 3 3 v4 = 4 4 4 4

现在我想要做的就是将它们加入到组合的角度来看，也就是

Now what I want to do is to add them combination-wise, that is,

v12 = v1+v2 v13 = v1+v3 v14 = v1+v4 v23 = v2+v3 v24 = v2+v4 v34 = v3+v4

直到这一步，这只是罚款。问题是，现在我要添加这些载体的每一个从V1，V2，V3一种载体，它已没有前加入V4。例如：

Till this step it is just fine. The problem is now I want to add each of these vectors one vector from v1, v2, v3, v4 which it hasn't added before. For example:

V3和V4还没有被添加到V12，所以我想创建V123和v124。同样，对于所有矢量喜欢，

v3 and v4 hasn't been added to v12, so I want to create v123 and v124. Similarly for all the vectors like,

v12 should become: v123 = v12+v3 v124 = v12+v4 v13 should become: v132 // This should not occur because I already have v123 v134 v14 should become: v142 // Cannot occur because I've v124 already v143 // Cannot occur v23 should become: v231 // Cannot occur v234 ... and so on.

这是我没有在一步一步地开始做是很重要的。例如像，我可以做（4选3）4C3和完成它，但我想这样做一步在每个迭代步骤。

It is important that I do not do all at one step at the start. Like for example, I can do (4 choose 3) 4C3 and finish it off, but I want to do it step by step at each iteration.

怎样编程呢？

PS：我想要工作的一个先验算法在数据挖掘中的一个修改版

P.S.: I'm trying to work on an modified version of an apriori algorithm in data mining.

推荐答案

在C ++中，给出了下面的程序：

In C++, given the following routine:

template <typename Iterator> inline bool next_combination(const Iterator first, Iterator k, const Iterator last) { /* Credits: Thomas Draper */ if ((first == last) || (first == k) || (last == k)) return false; Iterator itr1 = first; Iterator itr2 = last; ++itr1; if (last == itr1) return false; itr1 = last; --itr1; itr1 = k; --itr2; while (first != itr1) { if (*--itr1 < *itr2) { Iterator j = k; while (!(*itr1 < *j)) ++j; std::iter_swap(itr1,j); ++itr1; ++j; itr2 = k; std::rotate(itr1,j,last); while (last != j) { ++j; ++itr2; } std::rotate(k,itr2,last); return true; } } std::rotate(first,k,last); return false; }

您可以再继续执行以下操作：

You can then proceed to do the following:

int main() { unsigned int vec_idx[] = {0,1,2,3,4}; const std::size_t vec_idx_size = sizeof(vec_idx) / sizeof(unsigned int); { // All unique combinations of two vectors, for example, 5C2 std::size_t k = 2; do { std::cout << "Vector Indicies: "; for (std::size_t i = 0; i < k; ++i) { std::cout << vec_idx[i] << " "; } } while (next_combination(vec_idx, vec_idx + k, vec_idx + vec_idx_size)); } std::sort(vec_idx,vec_idx + vec_idx_size); { // All unique combinations of three vectors, for example, 5C3 std::size_t k = 3; do { std::cout << "Vector Indicies: "; for (std::size_t i = 0; i < k; ++i) { std::cout << vec_idx[i] << " "; } } while (next_combination(vec_idx, vec_idx + k, vec_idx + vec_idx_size)); } return 0; }

**注1：*由于迭代式接口的next_combination套路，任何 STL 支持着通过迭代器迭代的容器也可以使用，如的std ::矢量，的std :: deque的和的std ::列表只是仅举几例。

**Note 1:* Because of the iterator oriented interface for the next_combination routine, any STL container that supports forward iteration via iterators can also be used, such as std::vector, std::deque and std::list just to name a few.

注意2：这个问题是非常适合的记忆化技术的应用。在这个问题中，您可以创建一个地图，用给定的组合矢量和填充入。之前计算一组给定矢量的总和，可以查找以查看是否总和的任意子集已经计算出并使用这些结果。虽然你正在执行总和是相当便宜和快速，如果你执行的计算是要更为复杂和耗时，这种技术肯定会有助于带来一些重大的性能提升。

Note 2: This problem is well suited for the application of memoization techniques. In this problem, you can create a map and fill it in with vector sums of given combinations. Prior to computing the sum of a given set of vectors, you can lookup to see if any subset of the sums have already been calculated and use those results. Though you're performing summation which is quite cheap and fast, if the calculation you were performing was to be far more complex and time consuming, this technique would definitely help bring about some major performance improvements.