使用一个东西，不明白它的道理，不高明
——侯捷老师
1. is_permutation()函数
功能：判断两个序列是否是全排列关系
1.1 函数声明
// default(1)
template <class ForwardIterator1, class ForwardIterator2>
bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
// custom(2)
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
1.2 等价操作实现
template <class InputIterator1, class InputIterator2>
bool is_permutation (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2)
{
std::tie (first1,first2) = std::mismatch (first1,last1,first2);
if (first1==last1) return true;
InputIterator2 last2 = first2; std::advance (last2,std::distance(first1,last1));
for (InputIterator1 it1=first1; it1!=last1; ++it1) {
if (std::find(first1,it1,*it1)==it1) {
auto n = std::count (first2,last2,*it1);
if (n==0 || std::count (it1,last1,*it1)!=n) return false;
}
}
return true;
}
- std::tie()
- std::mismatch()
- std::advance()
1.3 示例程式
#include<array>
void test_is_permutation() {
std::array<int, 5> foo = {1,2,3,4,5};
std::array<int, 5> bar = {3,1,4,5,2};
if (std::is_permutation(foo.begin(), foo.end(), bar.begin())) {
cout << "foo and bar contain the same elements." << endl;
}
}
1.4 参考链接
http://www.cplusplus.com/reference/algorithm/is_permutation/
2. next_permutation()函数
功能：返回区间[first, last)下一个按字典排序大的全排列
2.1 函数声明
// default(1)
template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last);
// custom(2)
template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
2.2 源码探究
template<typename _BidirectionalIterator, typename _Compare>
inline bool
next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<
_BidirectionalIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
typename iterator_traits<_BidirectionalIterator>::value_type,
typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__next_permutation
(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
std::__next_permutation()函数
template<typename _BidirectionalIterator, typename _Compare>
bool
__next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
{
if (__first == __last)
return false;
_BidirectionalIterator __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;)
{
_BidirectionalIterator __ii = __i;
--__i;
if (__comp(__i, __ii))
{
_BidirectionalIterator __j = __last;
while (!__comp(__i, --__j))
{}
std::iter_swap(__i, __j);
std::__reverse(__ii, __last,
std::__iterator_category(__first));
return true;
}
if (__i == __first)
{
std::__reverse(__first, __last,
std::__iterator_category(__first));
return false;
}
}
}
2.3 示例程式
void test_next_permutation() {
int arr[] = {1, 3, 2};
std::sort(arr, arr+3);
cout << "the 3! possible permutation with 3 elements" << endl;
do {
std::cout << arr[0] << " " << arr[1] << " "<< arr[2] << endl;
} while (std::next_permutation(arr, arr+3));
cout << "After loop: " << arr[0] << " " << arr[1] << " " << arr[2] << endl;
}
输出结果：
image.png
2.4 参考链接
http://www.cplusplus.com/reference/algorithm/next_permutation/
3. perv_permutation()函数
功能：返回区间[first, last)下一个按字典排序小的全排列
3.1 函数声明
// default(1)
template <class BidirectionalIterator>
bool prev_permutation (BidirectionalIterator first,
BidirectionalIterator last );
// custom(2)
template <class BidirectionalIterator, class Compare>
bool prev_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
3.2 源码探究
perv_permutation()函数
template<typename _BidirectionalIterator, typename _Compare>
inline bool
prev_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<
_BidirectionalIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
typename iterator_traits<_BidirectionalIterator>::value_type,
typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__prev_permutation(__first, __last,
__gnu_cxx::__ops::__iter_comp_iter(__comp));
}
__prev_permutation()函数
template<typename _BidirectionalIterator, typename _Compare>
bool
__prev_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
{
if (__first == __last)
return false;
_BidirectionalIterator __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;)
{
_BidirectionalIterator __ii = __i;
--__i;
if (__comp(__ii, __i))
{
_BidirectionalIterator __j = __last;
while (!__comp(--__j, __i))
{}
std::iter_swap(__i, __j);
std::__reverse(__ii, __last,
std::__iterator_category(__first));
return true;
}
if (__i == __first)
{
std::__reverse(__first, __last,
std::__iterator_category(__first));
return false;
}
}
}
3.3 示例程式
void test_prev_permutation() {
int arr[] = {1, 3, 2};
std::sort(arr, arr+3, [](int i, int j) {
return i > j;
});
cout << "the 3! possible permutation with 3 elements" << endl;
do {
std::cout << arr[0] << " " << arr[1] << " "<< arr[2] << endl;
} while (std::prev_permutation(arr, arr+3));
cout << "After loop: " << arr[0] << " " << arr[1] << " " << arr[2] << endl;
}
输出结果：
image.png
3.4 参考链接
http://www.cplusplus.com/reference/algorithm/prev_permutation/
基于上述的next_permutation()和prev_permutation()返回全排列时，根据字典顺序排序的，下面列出其比较的规则:lexicographical_compare()函数
4. lexicographical_compare()函数
4.1 函数声明
// default(1)
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
// custom(2)
template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
4.2 示例程式
#include<string>
void test_lexicographical_compare() {
string str1 = "Hello";
string str2 = "haha";
std::cout << std::boolalpha;
cout << "Comparing foo and bar lexicographically(str1 < str2)" << endl;
cout << std::lexicographical_compare(str1.begin(), str1.end(), str2.begin(), str2.end()) << endl;
cout << "Using mycomp as comparision object: " << endl;
cout << std::lexicographical_compare(str1.begin(), str1.end(), str2.begin(), str2.end(),
[] (char c1, char c2){
return std::tolower(c1) < std::tolower(c2);
}) << endl;
}
输出结果：
image.png
4.3 参考链接
http://www.cplusplus.com/reference/algorithm/lexicographical_compare/
