さらに別のロジック

Question

私は好奇心のために研究上の問題に取り組んでいます。私が覚えているロジックをどのようにプログラムするのか分かりません。私はあなたにそれを説明してみましょう：

私は4つのベクトル、例えば言う、

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の1つのベクトルを追加します。たとえば、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 

私が最初に一つのステップでそれをすべてをしないことが重要です。例えば、私は4C3を選択して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; 
} 

NOTES：

1. trim関数モデル（最近発生した組み合わせと同じサイズ）指定されたキーサイズでメインマップからいくつかのエントリを削除し、あなたのブラックボックス
2. 私は」マップを反復して新しいエントリを挿入することの妥当性について確信が持てません（イテレータにどのように影響するか、それはうまくいくように見えますが、欠けているような微妙なものがあるかもしれないと思います。今すぐ！）
3. 検索のサイズを見つけるためにすべてのキーを繰り返し処理する必要があるため、パフォーマンスは理想的ではないかもしれません（組み合わせの場合）。
4. デバッグを取る場合は、あなたが実際のコードが非常に小さいことがわかります
5. すべてのベクトルは同じ大きさを持っている（これは自明に固定することができる）ことを前提としてい...
6. 組み合わせの順序保存されていない - これはあなたのため

EDIT必要があるかどうかわからない。今 オーケーbaseは、キー<ためpairを含むベクターである - >ベクトルの関係 - これは一定です。初期状態ではマップに追加され、関数は初期状態ではスキップされ、一部のエントリを削除するためにはまだtrimが呼び出されます。次の反復は同じ検索アルゴリズムを使用しますが、組み合わせはbaseの定数セットです。