2

想象一下，我们有一个只有唯一值的向量，并且想要生成所有对。这样做的算法是：

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 );
        }
    }
}

为四元组和其他元组类型编写代码相当容易。

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

谢谢！

4

1 回答 1

2

您所描述的称为k-combinations，这是组合学领域中一个非常重要的概念。一组n个元素中k个元素的唯一组合数用公式n表示！/（k！（nk）！）。

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

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

希望这对你来说足够清楚。:) 如果您还有其他问题，请随时要求更多解释。

于 2013-01-26T22:36:04.943 回答