next_permutation比较函数

Question

我想生成一个vector< pair<int,int> > v...的所有排列使用c ++ next_permutation,这样只有在v[i].first不考虑v[i].second... 的值的基础上生成排列...

v.push_back(pair<int,int>(3,600));

v.push_back(pair<int,int>(2,900));

v.push_back(pair<int,int>(2,800));

我需要遵循3个排列(处理(2,900)和(2,800)相同).

(2,900)(2,800)(3,600)

(2,900)(3,600)(2,800)

(3,600)(2,900)(2,800)

但相反,我得到6个排列((2,900)和(2,800)被处理不同)

我知道必须通过在next_permutation中使用比较器函数来完成....但我无法....请帮助如何使用比较器函数...

这是代码..

int main()
{
  vector< pair<int,int> > v;

  v.push_back(pair<int,int>(3,600));
  v.push_back(pair<int,int>(2,900));
  v.push_back(pair<int,int>(2,800));

  sort(v.begin(),v.end());

  do
  {
    for(int i=0; i<v.size(); i++)
    {
      printf("%d %d   ",v[i].first,v[i].second);
    }
    printf("\n");
   }while( next_permutation(v.begin(),v.end()) );

  return 0;
}

Answer 1

std::next_permutation接受可选的比较器作为其最后一个参数.功能定义是:

template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

您可以使用自定义比较器,仅比较该对的第一个成员:

using namespace std;

struct compareFirstPairMember {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        return a.first < b.first;
    }
};

然后获得所有排列(在具有相同比较器的排序向量上),是微不足道的:

int main() {

    vector<pair<int, int>> v;
    v.push_back(pair<int,int>(3,600));
    v.push_back(pair<int,int>(2,900));
    v.push_back(pair<int,int>(2,800));

    sort(v.begin(), v.end(), compareFirstPairMember());

    do {
        for(auto item : v)
          cout << item.first << " " << item.second << endl;
        cout << endl;
    } while ( std::next_permutation(begin(v), end(v), compareFirstPairMember()));

    return 0;
}

输出:

2 900 2 800 3 600

2 900 3 600 2 800

3 600 2 800 2 900

这里有实例.

编辑:

在C++ 11中,您可以使用lambda来内联比较函数:

std::next_permutation(begin(v), end(v), [](const pair<int, int>& a, const pair<int, int>& b) { return a.first < b.first; })