从一组集合{{中选择一组数字{1,2,3}.},{.},{.}}使得所有元素都是唯一的

Question

我感兴趣的是一种高效的算法来完成以下工作:

• 我有一组集合，每个集合由三个数字组成。
• 在此子集内，号码是唯一的。
• 但它们可以在其他子集中发生多次。
• 目标是选择例如3个子集，这样元素只有发生血一次。

例如

:{{1,2,3},{3、4、5},{6 7 8},{5、7、9}}

• 第二子集与第一子集有3个共同之处。
• 第4子集与第2和第3子集有一个共同的元素。
• 当现在选择多个子集时，这是不可能的。每个元素只能发生一次。

我实现了一个可以完成这项工作的东西，但我想可以更有效地完成。如何?也许会有一个恒定时间的map算法?

• 我使用list来实现集合，因为我删除了选中的或被排除的子集(快速移除)。
• 子集使用vector s实现。
• 为了跟踪已经选择的数字，我使用set。

看这里

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <iterator>
#include <algorithm>
#include <random>
using namespace std;
random_device rd;
mt19937 rng(rd());
// pickes a random entry from a vector and returns an iterator to that element.
list<vector<int>>::iterator randomEntry(list< vector<int> >& v)
{
  uniform_int_distribution<int> dis(0, v.size()-1); // guaranteed unbiased
  auto it{ begin(v) };
  advance(it, dis(rng));
  return it;
}
int main()
{
  // a collection of possible sets
  list< vector<int> > collection;
  collection.emplace_back( vector<int>{51,9,22} );
  collection.emplace_back( vector<int>{11,5,74} );
  collection.emplace_back( vector<int>{61,9,35} ); // 2nd element in common with 1st entry
  collection.emplace_back( vector<int>{19,54,66} );
  collection.emplace_back( vector<int>{53,86,35} ); // 3rd element in common with 3rd entry
  collection.emplace_back( vector<int>{11,3,55} ); // 1st element in common with 2nd entry
  // pick three -independent- sets form the collection
  vector< vector<int> > picked;
  set<int> elements;
  while(picked.size()<3)
  {
    auto entry{ randomEntry(collection) }; // iterator to a randomly choosen entry
    bool unused{ true };
    for(const auto i : *entry)
    {
      if( elements.find(i) != cend(elements)) // if it already exists in elements, its already used.
        unused= false;
    }
    if(unused)
      picked.emplace_back( *entry );
    collection.erase(entry); // in any chase, remove == don't pick it again.
  }
  // all the elements printed should only appear once.
  for(const auto& i : collection)
  {
    for(const auto j : i)
      cout<<j<<" ";
    cout<<endl;
  }
  return 0;
}

Answer 1

我有一组集合，每个集合由三个数字组成。

…目标是选择例如3个子集，这样元素只出现一次。

…但我想这样做会更有效率。如何?

因为你的目标是选取一个任意数目p的不相交子集(以3为例)，那么这就是集打包问题，它是Karp的21个np完全问题之一。

在问题中，您提到每个集合有3个元素(这次不是作为示例)。不幸的是，这个版本仍然是NPC。不过，幸运的是，这意味着存在一个近似算法，其系数为~50%。

因此，对于一般的p，你极不可能找到一个多项式时间算法来解决这个问题。看看你的代码，我怀疑它是正确的。它是一种(随机)贪婪算法，似乎有可能构建场景(输入+随机选择)，它将悲观地声称没有解决方案。

Answer 2

创建映射(c++中的散列)

遍历集合。

对于每个集合检查它的一个数字是否在映射中。如果没有，将数字添加到映射中，并将此集合添加到唯一集合中如果在映射中，继续到下一个集合。