c++ - 从 vector 生成元组(通用算法)

Question

假设我们有一个只有唯一值的 vector ，并且想要生成所有对。这样做的算法是:

vector< int > data;
// ... pushback some data

vector< vector< int > > pairs;

for( size_t i = 0; i < data.size() - 1; ++i )
{
    for( size_t j = i + 1; j < data.size(); ++j )
    {
        vector< int > pair; 
        pair.push_back( data[i] ); 
        pair.push_back( data[j] );

        pairs.push_back( pair );
    }
}

现在，对于三元组，算法更改为:

vector< int > data;
// ... pushback some data

vector< vector< int > > triples;

for( size_t i = 0; i < data.size() - 2; ++i )
{
    for( size_t j = i + 1; j < data.size() - 1; ++j )
    {
        for( size_t k = j + 1; k < data.size(); ++k )
        {
            vector< int > triple; 
            triple.push_back( data[i] ); 
            triple.push_back( data[j] );
            triple.push_back( data[k] );

            triples.push_back( triple );
        }
    }
}

想出四元组和其他元组类型的代码相当容易。

有人可以告诉我如何实现生成各种元组的通用算法吗？既然我们已经做到了，我该如何计算给定 vector 中元素数量的元组数量？对于对，公式为 n(n-1)/2。

谢谢!

Answer 1

您所描述的称为k-combinations，这是组合学领域中一个非常重要的概念。一组 n 元素中 k 元素的唯一组合数由公式 n!/(k!(n-k)!)。

要以通用方式有效解决此问题，您可能应该查看 std::tuple 和可变参数模板(C++11 功能)。但是，如果您不知道编译时的维数，则必须创建一个递归函数，该函数采用两个参数:所有项目的列表和k，即要从中选择的项目数列表。

然后，对于集合中的每个元素 e，创建一个列表，其中包含该元素以及以 k-1 作为要选择的数字递归调用函数的结果，并且仅提供列表中 e 之后的列表元素。这将防止在递归的多个子树中创建相同的子集。

希望您已经清楚了。 :) 如果您有任何其他问题，请随时寻求更多解释。