Хорошо, здесь, возможно, это можно сделать более эффективным, но я думаю, что это делает то, что вам нужно.
#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;
}
ПРИМЕЧАНИЯ:
- функция
trimмоделирует ваш черный ящик, который удаляет некоторые записи с главной карты с заданным размером ключа (такого же размера, как у последних сгенерированных комбинаций) - Я не уверен в правильности итерации карты и вставки новых записей(то есть как это влияет на итератор, похоже, что он работает, но я думаю, что я могу упустить что-то тонкое, чего мне не хватает - слишком поздно, чтобы думать об этом прямо сейчас!)быть идеальным, поскольку вам нужно перебрать все ключи, чтобы найти размер поиска (для комбинации).
- предполагает, что все векторы имеют одинаковый размер (но это можно исправить тривиально)
- ЕслиВы берете отладку, вы видите, что реальный код довольно мал ..
- Порядок комбинации не сохраняется - не уверен, если это необходимо для вас
РЕДАКТИРОВАТЬ: Хорошо, теперь base - это вектор, который содержит pair для ключевого <-> векторного отношения - это константа.Первоначально он добавляется на карту, и функция gen_comb пропускается для начального состояния, trim по-прежнему вызывается для удаления некоторых записей.Следующая итерация использует тот же алгоритм поиска, но комбинация с постоянным набором base с.