还有一个逻辑

Question

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

我有四个向量，例如，

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

做到这一步就可以了。现在的问题/技巧是，在每次迭代结束时，我将获得的向量放入黑盒函数中，它仅返回几个向量，例如 v12、v13 和 v34。现在，我想将这些向量中的每一个添加到之前未添加过的 v1、v2、v3、v4 中的一个向量。例如，v3和v4还没有添加到v12中，所以我想创建v123和v124。同样，对于所有向量，例如

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和v24 因为它被黑了 盒子功能，所以我们拥有的一切 可以使用的手是 v12、v13 和 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. 我不确定迭代的有效性地图并插入新条目（即它如何影响迭代器，它似乎有效，但我认为我可能遗漏了一些微妙的东西 - 现在考虑这个问题已经太晚了！）
3. 性能，可能不会是理想的，因为您需要迭代所有键来查找搜索大小（用于组合）。
4. 假设所有向量具有相同的大小（但这可以简单地修复）
5. 如果您进行调试，您会发现实际代码非常小。
6. 组合的顺序不会保留 - 不确定这是否是您需要

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