1

ベクトルのベクトルを使用して ID 番号を格納します。それらすべてを比較し、その中のすべての値が既に別の要素内にある要素を削除したいと思います。

このようなベクトルに4つの要素があるとします

[[1, 2, 3, 4], [1, 2, 3], [3], [1,2,3,5]]

この例では、2 番目と 3 番目の要素を削除する必要があります。

これを解決する最速のアルゴリズムは何でしょうか?

4

2 に答える 2

0

ここでは、要素の「一意性」だけでなく、「すでに別の要素の内部」の要件を満たすソリューションを提供します。

[[1、2、3、4]、[1、2、3]、[3]、[1,2,3,5]]の場合、出力は[[1、2、3、4]、[1 、2,3,5]]。

[[1、2、3、4]、[1、2、3]、[3,4]、[1,2,3,5]]の場合、出力は[[1、2、3、4]、 [1,2,3,5]]。

次のように機能します。

  1. 値をそのコンテナのベクトルにマップするマップを生成します
  2. ベクトルごとに、各値のコンテナーの交点を計算します。結果の交差に複数のアイテムがある場合（つまり、自己交差だけでなく）、そのようなベクトルは削除されます。
#include <boost/container/vector.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/assign/list_of.hpp>
#include <boost/unordered_map.hpp>
#include <boost/foreach.hpp>

#include <iterator>
#include <iostream>
#include <ostream>
#include <cstddef>
#include <string>

using namespace boost::assign;
using namespace boost;
using namespace std;

template<typename VecVec,typename OutputIterator>
void delete_included(const VecVec &vv,OutputIterator out)
{
    typedef typename range_value<VecVec>::type vec_type;
    typedef typename const vec_type *vec_id;
    typedef typename range_value<vec_type>::type value_type;

    unordered_map<value_type,container::vector<vec_id> > value_in;
    container::vector<vec_id> all_vec_indexes;
    BOOST_FOREACH(const vec_type &vec,vv)
    {
        all_vec_indexes.push_back(&vec);
        BOOST_FOREACH(const value_type &value,vec)
        {
            value_in[value].push_back(&vec);
        }
    }
    container::vector<vec_id> included_in;
    container::vector<vec_id> intersect;
    BOOST_FOREACH(const vec_type &vec,vv)
    {
        included_in=all_vec_indexes;
        BOOST_FOREACH(const value_type &value,vec)
        {
            intersect.clear();
            set_intersection(included_in,value_in[value],back_inserter(intersect));
            swap(included_in,intersect);
            if(included_in.size()==1)
                break;
        }
        if(included_in.size()==1)
        {
            *out=vec;
            ++out;
        }
    }
}
template<typename VecVec>
void print(const VecVec &vv)
{
    typedef typename range_value<VecVec>::type vec_type;
    typedef typename range_value<vec_type>::type value_type;

    cout << string(16,'_') << endl;
    BOOST_FOREACH(const vec_type &vec,vv)
    {
        copy(vec,ostream_iterator<const value_type&>(cout," "));
        cout << endl;
    }
}

int main(int argc,char *argv[])
{
    container::vector<container::vector<int> > vv
    (list_of
        ( list_of (1)(2)(3)(4) )
        ( list_of (1)(2)(3) )
        ( list_of (3) )
        ( list_of (1)(2)(3)(5) )
    );
    print(vv);

    container::vector<container::vector<int> > result;
    delete_included(vv,back_inserter(result));
    print(result);
    return 0;
}
于 2012-10-23T18:55:57.657 に答える
0

ここに考えられる解決策の 1 つがあります。

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>

typedef std::vector<int> VI;
typedef std::vector<std::vector<int>> VVI;

VVI DeleteDups(VVI vvi) {
  std::map<int,int> map;

  for(auto const& vi : vvi)
    for(auto const& i : vi)
      ++map[i];

  vvi.erase(
    std::remove_if(begin(vvi), end(vvi),
      [&map](const VI& vi)->bool {
        for(int i : vi)
          if(map[i] == 1) return false;
        return true;
      }),
    end(vvi));
  return vvi;
}

void Dump(const VVI& vvi) {
  std::cout << "[";
  for(auto const& vi : vvi) {
    std::cout << "[";
    for(int i : vi)
      std::cout << i << ", ";
    std::cout << "], ";
  }
  std::cout << "]\n";
}

int main () {
  Dump(DeleteDups({ {1,2,3,4}, {1,2,3}, {3}, {1,2,3,5} }));
}
于 2012-10-23T17:46:16.847 に答える