所有可能的组合。更快的方法

Question

我有一个 1 到 100 之间的数字向量（这并不重要），它的大小可以是 3 到 1.000.000 之间的值。

如果有人可以帮助我从该向量中获得 3 个值唯一*组合。

*唯一

示例：我在数组中有以下值：1[0] 5[1] 7[2] 8[3] 7[4]（[x] 是索引）

在本例中为 1[0] 5 [1] 7[2] 和 1[3] 5[1] 7[4] 不同，但 1[0] 5[1] 7[2] 和 7[2] 1[0] 5[1]是相同的（重复）

当我处理很多值时（例如 1.000.000），我的算法有点慢。所以我想要的是一种更快的方法。

           for(unsigned int x = 0;x<vect.size()-2;x++){
                for(unsigned int y = x+1;y<vect.size()-1;y++){
                    for(unsigned int z = y+1;z<vect.size();z++)
                    {

                        // do thing with vect[x],vect[y],vect[z]
                    }
                }
            }

Answer 1

事实上，您的值在 1 到 100 之间非常非常重要！因为对于大小为 1,000,000 的向量，您有很多相等的数字，并且您不需要检查所有这些数字！您可以执行以下操作：

注意：以下代码只是一个概要！它可能缺乏足够的错误检查，只是为了给您提供想法，而不是复制粘贴！

注2：当我写答案时，我假设数字在[0, 99]范围内。然后我读到它们实际上在 [1, 100] 中。显然这不是问题，您可以将所有数字设置为 -1，甚至更好，将所有 100 更改为 101。

bool exists[100] = {0};  // exists[i] means whether i exists in your vector

for (unsigned int i = 0, size = vect.size(); i < size; ++i)
    exists[vect[i]] = true;

然后，您可以执行与之前类似的操作：

for(unsigned int x = 0; x < 98; x++)
  if (exists[x])
    for(unsigned int y = x+1; y < 99; y++)
      if (exists[y])
        for(unsigned int z = y+1; z < 100; z++)
          if (exists[z])
          {
            // {x, y, z} is an answer
          }

您可以做的另一件事是花更多时间准备，以减少生成对的时间。例如：

int nums[100];  // from 0 to count are the numbers you have
int count = 0;

for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
  bool exists = false;
  for (int j = 0; j < count; ++j)
    if (vect[i] == nums[j])
    {
      exists = true;
      break;
    }
  if (!exists)
    nums[count++] = vect[i];
}

那么

for(unsigned int x = 0; x < count-2; x++)
  for(unsigned int y = x+1; y < count-1; y++)
    for(unsigned int z = y+1; z < count; z++)
    {
      // {nums[x], nums[y], nums[z]} is an answer
    }

让我们将 100 视为一个变量，因此我们将其称为 k，数组中存在的实际数字为 m（小于或等于到k）。

使用第一种方法，您需要 O(n) 准备工作和 O(m^2*k) 操作来搜索值，速度相当快。

在第二种方法中，您需要 O(nm) 准备工作和 O(m^3) 来生成值。鉴于您的 n 和 m 值，准备时间太长。

实际上，您可以合并这两种方法以获得两全其美的效果，如下所示：

int nums[100];           // from 0 to count are the numbers you have
int count = 0;
bool exists[100] = {0};  // exists[i] means whether i exists in your vector

for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
  if (!exists[vect[i]])
    nums[count++] = vect[i];
  exists[vect[i]] = true;
}

然后：

for(unsigned int x = 0; x < count-2; x++)
  for(unsigned int y = x+1; y < count-1; y++)
    for(unsigned int z = y+1; z < count; z++)
    {
      // {nums[x], nums[y], nums[z]} is an answer
    }

此方法具有 O(n) 准备工作和 O(m^3) 寻找独特三元组的成本。

编辑：事实证明，对于OP来说，不同位置的相同数字被认为是不同的值。如果真是这样的话，那么抱歉，没有更快的解决办法了。原因是所有可能的组合本身都是 C(n, m) （这是一个 组合），尽管您在 O(1) 中生成它们中的每一个，但它对您来说仍然太大了。

Answer 2

实际上没有什么可以加速你那里的循环体。考虑到向量大小为 1M，您将进行一万亿次循环迭代。

生成这样的所有组合是一个指数问题，这意味着当输入大小变得足够大时，您将无法实际解决它。如果可能的话，您唯一的选择是利用应用程序的特定知识（您需要结果的目的以及它们将如何使用）来“解决”问题。

Answer 3

也许您可以对输入进行排序，使其唯一，并在 a a 时选择 x[a]、x[b] 和 x[c]。 b＜ c.排序的时间复杂度为 O(n log n)，选择组合的时间复杂度为 O(n3)。不过，您需要迭代的三元组仍然会更少：

std::vector<int> x = original_vector;
std::sort(x.begin(), x.end());
std::erase(std::unique(x.begin(), x.end()), x.end());
for(a = 0; a < x.size() - 2; ++a)
  for(b=a+1; b < x.size() - 1; ++b)
     for(c=b+1; c< x.size(); ++c
        issue triplet(x[a],x[b],x[c]);

Answer 4

根据您的实际数据，您可以通过首先创建一个每个值最多包含三个条目的向量并对其进行迭代来显着加快速度。

Answer 5

正如 r15habh 指出的那样，我认为数组中的值在 1-100 之间这一事实实际上很重要。

您可以执行以下操作：遍历数组，将值读取到唯一的集合中。这个本身的时间复杂度是O(n)。该集合的元素不超过 100 个，这意味着空间复杂度为 O(1)。

现在，由于您需要生成所有 3 项排列，因此您仍然需要 3 个嵌套循环，但您将在最多包含 100 个元素的集合上进行操作，而不是在潜在的巨大数组上进行操作。

总体时间复杂度取决于您的原始数据集。对于小型数据集，时间复杂度将为 O(n^3)。对于大数据集，它将接近 O(n)。

Answer 6

如果正确理解您的应用程序，那么您可以使用元组，并根据您的要求存储在集合或哈希表中。如果三元组的法线很重要，那么请确保移动三元组，这样可以说最大的元素是第一个，如果法线不重要，那么只需对元组进行排序。使用 boost 和 的版本整数：

#include <set>
#include <algorithm>
#include "boost/tuple/tuple.hpp"
#include "boost/tuple/tuple_comparison.hpp"

int main()
{
    typedef boost::tuple< int, int, int > Tri;
    typedef std::set< Tri > TriSet;
    TriSet storage;
    // 1 duplicate
    int exampleData[4][3] = { { 1, 2, 3 }, { 2, 3, 6 }, { 5, 3, 2 }, { 2, 1, 3 } };
    for( unsigned int i = 0; i < sizeof( exampleData ) / sizeof( exampleData[0] ); ++i )    
    {
        std::sort( exampleData[i], exampleData[i] + ( sizeof( exampleData[i] ) / sizeof( exampleData[i][0] ) ) );
        if( !storage.insert( boost::make_tuple( exampleData[i][0], exampleData[i][1], exampleData[i][2] ) ).second )
            std::cout << "Duplicate!" << std::endl;
        else
            std::cout << "Not duplicate!" << std::endl;
    }
}