确定两个向量是否包含两个相邻的元素相同。

Question

我有一个问题，涉及确定两个向量是否包含两个相同的元素。元素可以位于向量的任何位置，但它们必须是相邻的。

更多示例：

例如，比较以下两个向量将返回false。

向量1 = [0, 1, 2, 3, 4, 6]

向量2 = [1, 4, 2, 0, 5, 3]

但是以下两个向量将返回true：

向量1 = [0, 1, 2, 3, 4, 5]

向量2 = [4, 2, 1, 5, 0, 3]

因为第一个向量中的1,2对应于第二个向量中的2,1。

真:

向量1 = [0, 1, 2, 3, 4, 5]

向量2 = [1, 4, 2, 0, 5, 3]

{5,0}是一对，尽管在向量上循环（我最初说这是假的，感谢'Vlad from Moscow'指出）。

真:

向量1 = [0, 1, 2, 3, 4, 5]

向量2 = [4, 8, 6, 2, 1, 5, 0, 3]

即使它们不在同一位置，{2,1}仍然是一对。

实际应用是，我有一个存储N个点的向量中的多边形（面）。为了确定一组多边形是否完全包围一个三维体积，我测试每个面以确保每个边都被另一个面共享（其中一条边由两个相邻点定义）。

因此，Face包含指向Points的指针向量...

std::vector<Point*> points_;

检查面是否被包围，可以使用Face类的成员函数...

bool isSurrounded(std::vector<Face*> * neighbours)
{
    int count = 0;
    for(auto&& i : *neighbours)     // for each potential face
        if (i != this)              // that is not this face
            for (int j = 0; j < nPoints(); j++) // and for each point in this face
                for (int k = 0; k < i->nPoints(); k++ ) // check if the neighbour has a shared point, and that the next point (backwards or forwards) is also shared
                    if ( ( this->at(j) == i->at(k) )        // Points are the same, check the next and previous point too to make a pair
                       && (    ( this->at((j+1)%nPoints()) == i->at((k+1)%(i->nPoints())) )
                            || ( this->at((j+1)%nPoints()) == i->at((k+i->nPoints()-1)%(i->nPoints())) )))
                        { count++; }
    if (count > nPoints() - 1) // number of egdes = nPoints -1
        return true;
    else
        return false;
}

显然，这段代码很糟糕。如果我两周后再来看它，可能就理解不了了。所以面对原始问题，你该如何清晰地检查这两个向量？

请注意，如果你试图解密提供的代码，“at(int)”返回一个面中的点，“nPoints()”返回一个面中的点数。

非常感谢。

- James

---

啊 - 又一个使用“两周规则”的人。 - Michael Burr

我应该指出这两个向量可以是任意长度。 - James

请提供更多的“不匹配”和“匹配”示例（不同长度，不同位置），包括边缘情况（开头/结尾 - 它们是否成对？） - Yakk - Adam Nevraumont

Answer 1

不够高效，但以下是一种可能性。

bool comparePair ( pair<int,int> p1, pair<int,int> p2 ) {
  return ( p1.first == p2.first && p1.second == p2.second )
           || ( p1.second == p2.first && p1.first == p2.second );
}

//....

vector< pair<int,int> > s1;
vector< pair<int,int> > s1;
vector< pair<int,int> > intersect( vec1.size() + vec2.size() );

for ( int i = 0; i < vec1.size()-1; i++ ) {
  pair<int, int> newPair;
  newPair.first = vec1[i];
  newPair.first = vec1[i+1];
  s1.push_back( newPair );
}

for ( int i = 0; i < vec2.size()-1; i++ ) {
  pair<int, int> newPair;
  newPair.first = vec2[i];
  newPair.first = vec2[i+1];
  s2.push_back( newPair );
}

auto it = std::set_intersection ( s1.begin(), s1.end(), s2.begin(), s2.end(), 
                                   intersect.begin(), comparePair );

return ( it != intersect.begin() ); // not sure about this.

- Abhishek Bansal

---

我喜欢它，因为它比我的代码更简洁，只用了一个循环。但是它也假设vec1和vec2的大小相同，这一点我应该进行说明 - 实际情况并非总是如此。 - James

啊，是的，但这突显了另一个问题，即两个元素可能不在向量中的相同位置。也许vec1中的前两个元素与vec2中的后两个元素匹配。 - James

@JamesHawkes 修改了我的答案。 - Abhishek Bansal

std::set_intersection 期望其输入已排序。此外，我猜 newPair.second = vec1[i+1]; 和 newPair.second = vec2[i+1]; 是笔误。 - Ali

Answer 2

如果我理解您的问题：

std::vector<int> a, b;
std::vector<int>::iterator itB = b.begin();
std::vector<int>::iterator itA;
std::vector<std::vector<int>::iterator> nears;
std::vector<int>::iterator near;
for(;itB!=b.end() ; ++itB) {
    itA = std::find(a.begin(), a.end(), *itB);
    if(nears.empty()) {
        nears.push_back(itA);
    } else {
     /* there's already one it, check the second */  
      if(*(++nears[0])==*itA && itA != a.end() {
        nears.push_back(itA);
      } else {
        nears.clear();
        itB--;
      }         
    }
    if(nears.size() == 2) {
      return true;
    } 
}
return false;

- Luca Davanzo

---

我明白你的想法，本质上是创建临时存储来跟踪一对。但是，你还必须检查--nears [0]是否存在相反的顺序以形成一对元素（我想？）。这是一个不错的思路，但我真的在寻找更简洁的解决方案。 - James

Answer 3

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

using namespace std;
class AdjacentSort
{
public:
    AdjacentSort(const vector<int>& ref);
    ~AdjacentSort();

    bool operator()(int e1,int e2) const;
private:
    const vector<int>& ref_;
};

AdjacentSort::AdjacentSort(const vector<int>& ref):
    ref_(ref)
{
}

bool AdjacentSort::operator()(int e1, int e2) const
{
    auto it1 = find(ref_.begin(),ref_.end(),e1);
    auto it2 = find(ref_.begin(),ref_.end(),e2);

    return distance(it1,it2) == 1;
}

AdjacentSort::~AdjacentSort()
{
}

int main()
{
    vector<int> vec {1,2,3,4,5};
    vector<int> vec2 {1,3,5,4,2};

    AdjacentSort func(vec);
    auto it = adjacent_find(vec2.begin(),vec2.end(),func);

    cout << *it << endl;

    return 0;
}

它返回第一个相邻数字出现的元素，否则返回尾迭代器。

- lucas92

---

这是我最喜欢的答案之一 - 尤其是如果我可以摆脱类并用lambda函数替换func。 - James

是的，这是可能的，但我发现将其分别在一个functor中实现更加优雅。 - lucas92

Answer 4

如果您的元素是相同的元素集，则为每个元素分配索引。 （伪代码中未提及特殊情况）：

for(int i=0;i<vect1.size;i++) {

   adj[vect1[i]][0] = vect1[i-1];
   adj[vect2[i]][1] = vect2[i+1];
}

for(int j=0;j<vect2.size();j++) {

    if(arr[vect2[i]][0]==(vect2[j-1] or vect[j+1]))
       return true
    if(arr[vect2[i]][1]==(vect2[j-1] or vect[j+1]))
       return true

}

- Vikram Bhat

Answer 5

如果我理解正确，这两个向量为：

std::vector<int> v1 = { 0, 1, 2, 3, 4, 5 };
std::vector<int> v2 = { 3, 5, 2, 1, 4, 0 };

包含相邻的相同元素。第一个向量中是一对 {1, 2}，第二个向量中是一对 {2, 1}，尽管这些对的位置在向量中不同。

实际上，您已经命名了可以在此任务中使用的合适的标准算法。它是std::adjacent_find。例如

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>


int main() 
{
    std::vector<int> v1 = { 0, 1, 2, 3, 4, 5 };
    std::vector<int> v2 = { 3, 5, 2, 1, 4, 0 };

    bool result =
        std::adjacent_find( v1.begin(), v1.end(),
            [&v2]( int x1, int y1 )
            {
                return std::adjacent_find( v2.begin(), v2.end(),
                [=]( int x2, int y2 ) 
                { 
                    return ( x1 == x2 && y1 == y2 || x1 == y2 && y1 == x2 );
                } ) != v2.end();
            } ) != v1.end();

    std::cout << "result = " << std::boolalpha << result << std::endl;

    return 0;
}

- Vlad from Moscow

---

我认为这是一个有趣的想法。然而，原帖的问题要求将向量的最后一个元素和第一个元素视为相邻的（这并没有说明得很清楚）。std::adjacent_if并不会这样做，但是加入几行额外的代码就可以测试这种情况并完成你的答案了。 - Cassio Neri

如果@Cassio所说的确实正确，那么这两个向量 向量1 = [0, 1, 2, 3, 4, 5]向量2 = [1, 4, 2, 0, 5, 3] 有相邻的相等对{0, 5}。然而，在原帖中并没有提到这一对存在。 - Vlad from Moscow

你们两个都是正确的，我确实是指最后一个和第一个元素应该被视为相邻的，并且我给出了一个糟糕的例子。我已经编辑了我的帖子以反映这一点。不过这是一个非常有趣的答案，我需要更深入地研究std::adjacent_find()。 - James

Answer 6

这是我尝试解决这个问题的方法。简单地遍历 a，在 b 中找到相同的元素，然后将 a 中的下一个元素与我们在 b 中的位置之前和之后的元素进行比较。

如果它比需要的更啰嗦一些，那是因为这个函数可以用于任何容器。唯一的要求是容器的迭代器必须是双向的。

    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <list>

    using namespace std;

    template <class Iter>
    pair<Iter, Iter> get_neighbors(Iter begin, Iter current, Iter end)
    {
        auto p = make_pair(end, next(current));
        if(current != begin)
            p.first = prev(current);
        return p;
    }

    template <class Iter1, class Iter2>
    bool compare_if_valid(Iter1 p1, Iter1 end1, Iter2 p2)
    {
        return p1 != end1 && *p1 == *p2;
    }

    template <class C1, class C2>
    auto neighbors_match(const C1 & a, const C2 & b) ->
        decltype(make_pair(begin(a), begin(b)))
    {
        for(auto i = begin(a); i != end(a) && next(i) != end(a); ++i)
        {
            auto pos_in_b = find(begin(b), end(b), *i);
            if(pos_in_b != end(b))
            {
                auto b_neighbors = get_neighbors(begin(b), pos_in_b, end(b));
                if(compare_if_valid(b_neighbors.first, end(b), next(i)))
                    return {i, b_neighbors.first};
                else if(compare_if_valid(b_neighbors.second, end(b), next(i)))
                    return {i, pos_in_b};
            }
        }
        return {end(a), end(b)};
    }

    int main()
    {
        vector<int> a = {0, 1, 2, 3, 4, 5};
        vector<int> b = {1, 4, 2, 0, 5, 3};
        cout << boolalpha << (neighbors_match(a, b).first != a.end()) << endl;
        vector<int> a2 = {0, 1, 2, 3, 4, 5};
        list<int> b2 = {4, 2, 1, 5, 0, 3};
        auto match = neighbors_match(a2, b2);
        cout << boolalpha << distance(a2.cbegin(), match.first)
             << ' ' << distance(b2.cbegin(), match.second) << endl;
        return 0;
    }

- SirGuy

---

我喜欢它适用于不同类型的容器 - 但你是对的，这确实使它变得非常冗长！ - James

Answer 7

你实际上正在询问的是两个面（我们称之为a和b）的边集是否“不相交”。这可以分解为是否存在于a中的任何边也在b中，这只是一个成员测试问题。然而，向量在成员测试方面并不出色。

我的解决方案是将其中一个向量转换为unordered_set< pair<int, int> >。 unordered_set只是一个哈希表，而对偶表示边。

在表示边时，我采用了归一化方案，其中顶点的索引按递增顺序排列（因此，[2,1]和[1,2]都被存储为[1,2]在我的边集中）。这使得相等性测试变得更加容易（即仅与对偶相等）。

所以这是我的解决方案：

#include <iostream>
#include <utility>
#include <functional>
#include <vector>
#include <unordered_set>
using namespace std;

using uint = unsigned int;
using pii = pair<int,int>;

// Simple hashing for pairs of integers
struct pii_hash {
    inline size_t
    operator()(const pii & p) const
    {
        return p.first ^ p.second;
    }
};

// Order pairs of integers so the smallest number is first
pii ord_pii(int x, int y) { return x < y ? pii(x, y) : pii(y, x); }

bool
shares_edge(vector<int> a, vector<int> b)
{
    unordered_set<pii, pii_hash> edge_set {};

    // Create unordered set of pairs (the Edge Set)
    for(uint i = 0; i < a.size() - 1; ++i)
        edge_set.emplace( ord_pii(a[i], a[i+1]) );

    // Check if any edges in B are in the Edge Set of A
    for(uint i = 0; i < b.size() - i; ++i)
    {
        pii edge( ord_pii(b[i], b[i+1]) );

        if( edge_set.find(edge) != edge_set.end() )
            return true;
    }

    return false;
}

int main() {
    vector<int>
        a {0, 1, 2, 3, 4, 5},
        b {1, 4, 2, 0, 5, 3},
        c {4, 2, 1, 0, 5, 3};

    shares_edge(a, b); // false
    shares_edge(a, c); // true

    return 0;
}

在您的特定情况下，您可能希望将 shares_edge 设为您的 Face 类的成员函数。还可以预先计算边集并将其存储为 Face 的实例变量，但这取决于边数据更改的频率与此计算发生的频率。

编辑 额外解决方案

编辑2 修正了问题更改：边集现在包裹点列表。

如果您添加了在初始化时预计算的边集到某种 Face 类中，则会出现以下内容。私有嵌套的 Edge 类可以被认为是用实际类装饰您当前表示边的方式（即点列表中的两个相邻位置），因此像 set 这样的集合可以将索引视为实际边：

#include <cassert>
#include <iostream>
#include <utility>
#include <functional>
#include <vector>
#include <unordered_set>

using uint = unsigned int;

class Face {
    struct Edge {
        int  _index;
        const std::vector<int> *_vertList;

        Edge(int index, const std::vector<int> *vertList)
            : _index {index}
            , _vertList {vertList}
        {};

        bool
        operator==(const Edge & other) const
        {
            return
                ( elem() == other.elem() && next() == other.next() ) ||
                ( elem() == other.next() && next() == other.elem() );
        }

        struct hash {
            inline size_t
            operator()(const Edge & e) const
            {
                return e.elem() ^ e.next();
            }
        };

    private:
        inline int elem() const { return _vertList->at(_index); }

        inline int
        next() const
        {
            return _vertList->at( (_index + 1) % _vertList->size() );
        }
    };

    std::vector<int>                     _vertList;
    std::unordered_set<Edge, Edge::hash> _edgeSet;

public:

    Face(std::initializer_list<int> verts)
        : _vertList {verts}
        , _edgeSet {}
    {
        for(uint i = 0; i < _vertList.size(); ++i)
            _edgeSet.emplace( Edge(i, &_vertList) );
    }

    bool
    shares_edge(const Face & that) const
    {
        for(const Edge & e : that._edgeSet)
            if( _edgeSet.find(e) != _edgeSet.end() )
                return true;

        return false;
    }

};

int main() {

    Face
        a {0, 1, 2, 3, 4, 5},
        b {1, 4, 2, 0, 5, 3},
        c {4, 2, 1, 0, 5, 3},
        d {0, 1, 2, 3, 4, 6},
        e {4, 8, 6, 2, 1, 5, 0, 3};

    assert( !d.shares_edge(b) );
    assert(  a.shares_edge(b) );
    assert(  a.shares_edge(c) );
    assert(  a.shares_edge(e) );

    return 0;
}

正如您所看到的，这种增加的抽象使得shares_edge()的实现非常令人愉悦，但这是因为真正的诀窍在于Edge类的定义（或更具体地说是e1 == e2 <=> Edge::hash(e1) == Edge::hash(e2)这种关系）。

- amnn

---

这很酷。在我的应用程序中，我从“点”创建“面”，然后创建3D多面体。我可以将“边缘”添加到此系统中，并创建成员函数以进行相等比较，这可能是最整洁的解决方案 - 但我决定按顺序存储点就足够了。感谢您的回复！ - James

不需要明确添加 Edge。在初始化时，Face类生成其边集即可，同时仍保留对点的有序列表的引用（这对于实际绘图命令可能很有用）。我已经向我的答案中添加了一个额外的解决方案，将边集添加到 Face 类中，另外还有点的列表。 - amnn

Answer 8

一个有趣的“你会如何做…”问题… :-) 它让我从为表单添加编辑框和组合框中休息了15分钟，换了些编程… LOL

所以，这是我认为我会怎么做…

首先，我会将边缘定义为一对值（一对int - 遵循您原始示例）。我意识到您的示例只是一个简化，实际上您正在使用自己类的向量（Point*而不是int？）但应该很容易将此代码模板化并使用任何类型。

#include <stdlib.h>
#include <iostream>
#include <vector>
#include <set>
#include <vector>
using namespace std;

typedef pair<int, int> edge;

然后我会创建一个集合类（set class），它将按我们需要的方式保持其元素（边缘）有序（通过比较边缘顺序不敏感的方式 - 即如果 e1.first==e2.first 并且 e1.second==e2.second，则边缘 e1 和 e2 相同，但如果 e1.first==e2.second 并且 e1.second==e2.first，则它们也相同）。为此，我们可以创建一个函数：

struct order_insensitive_pair_less
{
    bool operator() (const edge& e1, const edge& e2) const
    {
        if(min(e1.first,e1.second)<min(e2.first,e2.second)) return true;
        else if(min(e1.first,e1.second)>min(e2.first,e2.second)) return false;
        else return(max(e1.first,e1.second)<max(e2.first,e2.second));
    }
};

最后，我们的辅助类（称之为edge_set）将是一个简单的集合派生类，使用上述功能进行排序，并添加了一些方便的方法 - 一个构造函数，从向量（或实践中的Face类）填充集合，以及一个测试函数（bool shares_edge(const vector&v)），告诉我们该集合是否与另一个共享边缘。因此：

struct edge_set : public set<edge, order_insensitive_pair_less>
{
    edge_set(const vector<int>&v);
    bool shares_edge(const vector<int>&v);
};

实现为：

edge_set::edge_set(const std::vector<int>&v) : set<edge, order_insensitive_pair_less>()
{
    if(v.size()<2) return; // assume there must be at least 2 elements in the vector since it is supposed to be a list of edges...
    for (std::vector<int>::const_iterator it = v.begin()+1; it != v.end(); it++)
        insert(edge(*(it-1), *it));
}

bool edge_set::shares_edge(const std::vector<int>& v)
{
    edge_set es(v);
    for(iterator es_it = begin(); es_it != end(); es_it++)
        if(es.count(*es_it))
            return true;
    return false;
}

使用起来就变得非常简单（而且相当优雅）。假设您在变量v1和v2中拥有您在问题摘要中提供的两个向量作为示例，要测试它们是否共享一个边缘，您只需要编写：

if(edge_set(v1).shares_edge(v2))
    // Yup, they share an edge, do something about it...
else
    // Nope, not these two... Do something different...

这种方法对元素数量的唯一假设是每个向量至少有2个元素（因为没有至少2个顶点就不能有“边”）。但即使不是这种情况（其中一个向量为空或只有一个元素），也会导致空的edge_set，因此您将得到一个答案，即它们没有共享的边缘（因为其中一个集合为空）。没什么大不了的...我认为，以这种方式进行操作肯定会通过“两周测试”，因为您可以拥有一个专用类，在其中可以有几行注释来说明它正在做什么，实际比较非常易读（edge_set（v1）.shares_edge（v2））...

- marko

---

非常详细的回答，我很感激。如果我在代码中从多个地方调用它，我可能会像你一样将其拆分，以便我可以随时使用简单的函数调用。然而，由于这是我只会在一个子程序中执行的操作，我试图避免过度抽象并保持内联。 - James

Answer 9

我认为这是我所能想到的最简洁的表达方式。

bool check_for_pairs(std::vector<int> A, std::vector<int> B) {
  auto lastA = A.back();
  for (auto a : A) {
    auto lastB = B.back();
    for (auto b : B) {
      if ((b == a && lastB == lastA) || (b == lastA && lastB == a)) return true;
      lastB = b;
    }
    lastA = a;
  }
  return false;
}

更高效的方法是使用集合。

bool check_for_pairs2(std::vector<int> A, std::vector<int> B) {
  using pair = std::pair<int,int>;
  std::unordered_set< pair, boost::hash<pair> > lookup;
  auto last = A.back();
  for (auto a : A) {
    lookup.insert(a < last ? std::make_pair(a,last) : std::make_pair(last,a));
    last = a;
  }
  last = B.back();
  for (auto b : B) {
    if (lookup.count(b < last ? std::make_pair(b,last) : std::make_pair(last,b)))
      return true;
    last = b;
  }
  return false;
}

如果你实现了一个哈希函数，将 (a,b) 和 (b,a) 哈希到同一个值，那么你可以去掉检查哪个值更小的步骤。

- Silas

Answer 10

首先，编写一个 make_paired_range_view 函数，它接受一个范围并返回一个范围，其迭代器返回 std::tie(*it, *std::next(it))。在此处可以使用 boost，因为它们的迭代器编写代码使这个过程变得不那么繁琐。

接下来，unordered_equal 接受两个 pair 并比较它们，忽略顺序（因此如果第一个相等且第二个也相等，或者第一个等于另一个的第二个，反之亦然，则它们相等）。

现在，我们使用 unordered_equal 在右侧中查找每个左侧的配对。

这样做的优点是不需要额外的内存，但缺点是时间复杂度为 O(n^2)。

如果我们更关心时间而不是内存，我们可以将pair排序后，将其放入unordered_set中，以此来代替先前的方法。然后我们遍历第二个容器，对于每个pair（经过排序后），检查它是否在unordered_set中存在。这需要额外的O(n)内存，但运行时间为O(n)。也可以不使用向量和范围写法进行操作。

如果元素比int更昂贵，您可以编写一个自定义的pseudo_pair，其中包含指针，并基于指针内容确定其哈希值和相等性。

- Yakk - Adam Nevraumont

---

对于使用pair和unordered_set方法，我给予+1的推荐。虽然这样做会导致一个本应简单的算法变得过于抽象。 - James