Algorithms - Lexicographical

Overview

A lexicographical comparison is the kind of comparison generally used to sort words alphabetically in dictionaries; It involves comparing sequentially the elements that have the same position in both ranges against each other until one element is not equivalent to the other. The result of comparing these first non-matching elements is the result of the lexicographical comparison.

Lexicographical algorithms  operate on various types of containers such as sequence, associative and unordered to perform lexicographical actions such as comparing elements, generate sequences etc.

These function accepts parameters like 

• iterators such as input, bidirectional
• predicates such as binary 

The parameter type  Compare is a function that accepts two inputs and returns bool value (true or false). auto caseless = [](char a, char b) {return (tolower(a) < tolower(b)); };

For example, bool caseless (char a, char b) {(tolower(a) < tolower(b)); } or 

[](char a, char b) {(tolower(a) < tolower(b));}

Details

Name	Description
bool lexicographical_compare ( InputIterator first, InputIterator last,  InputIterator2 first2, InputIterator2 last2) bool lexicographical_compare ( InputIterator first, InputIterator last,  InputIterator2 first2, InputIterator2 last2,  Compare comp)	Returns true if the range [first,last] compares lexicographically less than the range [first2,last2]. Characters are compared left to right, one to one.  Following rules are applied. [a..z]  > [A..Z]  >  [0..9]
Example string ab{"ab"}, abcd{"abcd"},abcD{"abcD"} ,abc4{"abc4"}, abCd{"abCd"}; auto caseless = [](char a, char b) {return (tolower(a) < tolower(b)); }; cout << boolalpha; //1 //prints true cout << lexicographical_compare(begin(ab), end(ab), begin(abcd), end(abcd)) << endl; //prints true cout << lexicographical_compare(begin(abcD), end(abcD), begin(abcd), end(abcd)) << endl; //prints true cout << lexicographical_compare(begin(abc4), end(abc4), begin(abcD), end(abcD)) << endl; //prints false cout << lexicographical_compare(begin(abcD), end(abcD), begin(abCd), end(abCd)) << endl; //2 //prints true cout << lexicographical_compare(begin(ab), end(ab), begin(abcd), end(abcd), caseless) << endl; //prints false cout << lexicographical_compare(begin(abcD), end(abcD), begin(abcd), end(abcd), caseless) << endl; //prints true cout << lexicographical_compare(begin(abc4), end(abc4), begin(abcD), end(abcD), caseless) << endl; //prints false cout << lexicographical_compare(begin(abcD), end(abcD), begin(abCd), end(abCd), caseless) << endl;
bool next_permutation ( BidirectionalIterator first, BidirectionalIterator last) bool next_permutation ( BidirectionalIterator first, BidirectionalIterator last, Compare comp)	Rearranges the elements in the range [first,last] into the next lexicographically greater permutation. The comparisons of individual elements are performed using either operator< for the first version, or comp for the second. A permutation is each one of the N! possible arrangements the elements. The first permutation is the one which has all its elements sorted in ascending order, and the largest permutation has all its elements sorted in descending order. If the function can determine the next higher permutation, it rearranges the elements as such and returns true. If that was not possible, it rearranges the elements according to the first permutation and returns false.
Example string s; cout << boolalpha; //1 /* Prints abc Permutation?:true value:acb acb Permutation?:true value:bac bac Permutation?:true value:bca bca Permutation?:true value:cab cab Permutation?:true value:cba cba Permutation?:false value:abc */ s.assign("abc"); cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << endl; //2 /* Prints cba Permutation?:true value:cab cab Permutation?:true value:bca bca Permutation?:true value:bac bac Permutation?:true value:acb acb Permutation?:true value:abc abc Permutation?:false value:cba */ s.assign("cba"); cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << next_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl;
bool prev_permutation ( BidirectionalIterator first, BidirectionalIterator last) bool prev_permutation ( BidirectionalIterator first, BidirectionalIterator last, Compare comp)	Same as  next_permutation except elements are arranged in lexicographically lesser permutation.
Example string s; cout << boolalpha; //1 /* Prints cba Permutation?:true value:cab cab Permutation?:true value:bca bca Permutation?:true value:bac bac Permutation?:true value:acb acb Permutation?:true value:abc abc Permutation?:false value:cba */ s.assign("cba"); cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s)) << "\t value:" << s << endl; cout << endl; //2 /* Prints abc Permutation?:true value:acb acb Permutation?:true value:bac bac Permutation?:true value:bca bca Permutation?:true value:cab cab Permutation?:true value:cba cba Permutation?:false value:abc */ s.assign("abc"); cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl; cout << s << "\tPermutation?:" << prev_permutation(begin(s), end(s), greater<int>()) << "\t value:" << s << endl;

The example depicts the usage.

Summary of Examples

Name	Description	github	wandbox
Example	Usage	source    output	source + output