Еще одна логика

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. I» m не уверен в правильности итерации через карту и вставке новых записей (то есть, как она влияет на итератор, она работает, но я думаю, что может быть что-то тонкое, что мне не хватает - слишком поздно ночью думать о это прямо сейчас!)
3. Производительность, возможно, не идеальна, так как вам нужно перебирать все ключи, чтобы найти размер поиска (для комбинации).
4. предполагает, что все векторы имеют одинаковый размер (но это может быть исправлено тривиально)
5. Если вы достаньте отладки, вы увидите, что фактический код достаточно мал ..
6. Порядок комбинации не сохраняется - не уверен, если это необходимо для вас

EDIT: Хорошо, теперь base вектор, который содержит pair для ключа < -> вектор отношений - это константа. Первоначально он добавляется к карте, а функция gen_comb пропускается для исходного состояния, trim по-прежнему вызывается для удаления некоторых записей. Следующая итерация использует тот же алгоритм поиска, но комбинация с постоянным набором base s.