Okay, here goes, this probably could be made more efficient, but I think this does what you need.
#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;
}
NOTES:
- the
trim function models your black box which removes some entries from the main map with a given key size (same size as the most recently generated combinations)
- I'm not sure about the validity of iterating through the map and inserting new entries (i.e. how it impacts the iterator, it appears to work, but I think there may be something subtle that I am missing - it's far too late at night to think about that right now!)
- Performance, may not be ideal, as you need to iterate through all keys to find the search size (for combination).
- assumes that all vectors have the same size (but this can be fixed trivially)
- If you take out the debug, you'll see that the actual code is quite small..
- The order of the combination is not preserved - not sure if this is necessary for you
EDIT:
Okay now base is a vector which contains a pair for the key<->vector relationship - this is constant. Initially it is added to the map, and the gen_comb function is skipped for the initial state, trim is still called to remove some entries. Next iteration uses the same search algorithm, but the combination is with the constant set of bases.
