c++ - 又一个逻辑

Question

出于好奇，我正在研究一个研究问题，但我不知道如何对我想到的逻辑进行编程。让我向您解释一下:

我有四个 vector ，例如，

v1 = 1 1 1 1
v2 = 2 2 2 2
v3 = 3 3 3 3
v4 = 4 4 4 4

我想组合添加它们。也就是说，

v12 = v1+v2
v13 = v1+v3
v14 = v1+v4
v23 = v2+v3
v24 = v2+v4
v34 = v3+v4

到这一步就好了。现在的问题/技巧是，在每次迭代结束时，我将获得的 vector 输入黑盒函数，它只返回少数 vector ，比如 v12、v13 和 v34。现在，我想为这些 vector 中的每一个添加一个来自 v1、v2、v3、v4 的 vector ，它以前没有添加过。例如v3和v4还没有添加到v12，所以我想创建v123和v124。同样，对于所有 vector ，

v12 should become:
v123 = v12+v3
v124 = v12+v4

v13 should become:
v132 // This should not occur because I already have v123
v134 = v13+v4;

v14,v23 and v24 cannot be considered because it was deleted in the black box function so all we have in our hands to work with is v12,v13 and v34.

v34 should become:
v341 // Cannot occur because we have 134
v342 = v34+v2

重要的是我不要在一开始就一步完成所有的事情。例如，我可以做(4 选 3)4C3 并完成它，但我想在每次迭代时逐步完成。

包含黑盒功能怎么办？

Answer 1

好的，开始吧，这可能会变得更有效率，但我认为这可以满足您的需要。

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

typedef vector<int> v_t;
typedef set<int> s_t;
typedef map<s_t, v_t> m_t;
typedef vector<pair<s_t, v_t> > b_t;

// this inserts a new entry into the map with the provided key
// the value_type (vector) is generated by adding the entries in each vector
// NOTE: the first vector is passed by value (so we get a copy in the function)
// the second vector (passed by ref) is then added to it.
void insert_entry(m_t& dest, s_t& key, v_t vdest, v_t const& v2)
{
  v_t::const_iterator it2(v2.begin());
  // there is no global operator+ for vector, so you have to do something like below
  for(v_t::iterator it(vdest.begin()), end(vdest.end()); it != end && (*(it++) += *(it2++)););
  // this is just debug
  cout << "new key: " << key.size() << " : ";
  copy(key.begin(), key.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  cout << "vec: ";
  copy(vdest.begin(), vdest.end(), ostream_iterator<int>(cout, " "));
  // actual insert in to map
  // for example, key may be set<1, 2> and value is vector <3, 3, 3, 3>
  dest.insert(dest.end(), make_pair(key, vdest));
  cout << "size of dest: " << dest.size() << endl;
}

// This function generates all unique combinations of a given size and inserts them into 
// the main map
void gen_comb(size_t cmb, b_t const& base, m_t& dest)
{
  typedef m_t::iterator m_it;

  cout << "combination size: " << cmb << endl;

  // Now calculate our starting vector key size, a "key" is imply a combination of
  // vectors, e.g. v12, v23 v14 etc. in this case key size = 2 (i.e. two vectors)
  // If we need to generate combinations of size 3 (cmb=3), then we start with all
  // vectors of key size = 2 (v12, v23, v14 etc.) and add all the base (v1, v2 v3) to it
  size_t s_ksz = cmb - 1; // search key size
  cout << "search size: " << s_ksz << endl;
  // now iterate through all entries in the map
  for(m_it it(dest.begin()); it != dest.end(); ++it)
  {
    // Aha, the key size matches what we require (for example, to generate v123, we
    // need v12 (key size == 2) first
    if (it->first.size() == s_ksz)
    {
      // Now iterate through all base vectors (v1, v2, v3, v4)
      for(b_t::const_iterator v_it(base.begin()), v_end(base.end()); v_it != v_end; ++v_it)
      {
        // new key, start with the main key from map, e.g. set<1, 2>
        s_t nk(it->first.begin(), it->first.end());
        // Add the base key set<3>, reason I do it this way is that, in case you
        // that base vectors should be other than size 1 (else insert(*((*v_it)->first.begin())) should work just fine.
        nk.insert(v_it->first.begin(), v_it->first.end());
        // check if this key exists, this is the main check, this tests whether our map
        // already has a key with the same vectors (for example, set<1,2,3> == set<2,3,1> - internally set is ordered)
        m_it k_e = dest.find(nk);
        // If the key (combination of vectors) does not exist, then insert a new entry
        if (k_e == dest.end())
        {
          // new key
          insert_entry(dest, nk, it->second, v_it->second);
        }
      }
    }
  }
}

void trim(size_t depth, m_t& dest)
{
  for(m_t::iterator it(dest.begin()); it != dest.end();)
  {
    if (it->first.size() == depth && (rand() % 2))
    {
      cout << "removing key: " << depth << " : ";
      copy(it->first.begin(), it->first.end(), ostream_iterator<int>(cout, " "));
      cout << endl;
      dest.erase(it++);
    }
    else
      ++it;
  }
}

int main(void)
{
  // combination map
  m_t dest;

  // this is the set of bases
  b_t bases;
  int max_i = 4;
  for(int i = 1; i <= max_i; ++i)
  {
    v_t v(4, i);
    s_t k;
    k.insert(i);
    bases.push_back(make_pair(k, v));
  }

  // for the start, push in the bases
  dest.insert(bases.begin(), bases.end());

  // for each combination size, generate a new set of vectors and then trim that set.
  for (size_t cmb = 1; cmb <= static_cast<size_t>(max_i); ++cmb)
  {
    if (cmb > 1) gen_comb(cmb, bases, dest);
    trim(cmb, dest); // randomly remove some entries...
  }


  return 0;
}

注意事项:

1. trim 函数对您的黑匣子进行建模，该黑匣子使用给定键大小(与最近生成的组合大小相同)从主映射中删除一些条目
2. 我不确定遍历 map 和插入新条目的有效性(即它如何影响迭代器，它似乎有效，但我认为我可能遗漏了一些微妙的东西 - 为时已晚晚上想想现在!)
3. 性能可能不理想，因为您需要遍历所有键以找到搜索大小(用于组合)。
4. 假设所有 vector 都具有相同的大小(但这可以很容易地固定)
5. 如果你去掉debug，你会发现实际的代码非常小..
6. 组合的顺序未保留 - 不确定这对您是否有必要

编辑: 好的，现在 base 是一个 vector ，其中包含用于键 <-> vector 关系的 对 - 这是常数。最初它被添加到 map 中，并且为初始状态跳过了 gen_comb 函数，仍然调用 trim 来删除一些条目。下一次迭代使用相同的搜索算法，但组合是 base 的常量集。