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

Question

我对执行以下工作的高效算法很感兴趣:

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

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

• 第二个子集与第一个子集有 3 个共同点。
• 第 4 个子集与第 2 个和第 3 个子集有一个共同的元素。
• 当现在选择了多个子集时，那是不可能的。每个元素只能出现一次。

我实现了一个可以完成这项工作的东西，但我想这样做可以更有效率。如何？甚至可能有一个带有 map 左右的恒定时间算法吗？

• 我使用 list 来实现集合，因为我删除了 picked 或排除的子集(快速删除)。
• 子集是使用 vector 实现的。
• 为了跟踪已经选择的号码，我使用了一个集合。

Watch it here.

#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

I've a set of sets that are comprised of three numbers each.

... The target is to pick e.g. 3 subsets, such that the elements are only occure once.

... but I guess that can be done more efficient. How?

由于您的目标是选择任意数量 p 的不相交子集(以 3 为例)，那么这正是 Set Packing problem , 这是 Karp's 21 NP-complete problems 之一.

在问题中，您提到每个集合有 3 个元素(这次不作为示例)。可惜这个版本还是NPC。幸运的是，这意味着 there is an approximation algorithm with with a factor of ~50% .

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