“Lexicographically” refers to organizing the order of words or strings based on their individual characters arranged alphabetically. This simply means “dictionary order”. Let’s understand the concept of lexicographical order in detail and explore how to use it in programming world.
What is a lexicographic order?
Lexicographical order refers to the arrangement of strings or elements based on their alphabetical order. These arrangements are just like one would find in a dictionary that’s why it is also known as “Dictionary order”. This order compares elements character by character from left to right, and the first difference between two elements determines their relative position.
Let’s understand this concept with an example.
The below example shows you a list containing the prime numbers.{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
When we arrange these numbers in lexicographical order the list becomes:{11, 13, 17, 19, 2, 23, 29, 3, 5, 7}
Here’s how the transformation occurs:
- The numbers starting with “1” are listed first in ascending order because the next digit after “1” is compared: 11, 13, 17, and 19.
- Following these, the number starting with “2” is considered next, as “2” comes after “1” in the order of single digits: 2, 23, and 29.
- Finally, the numbers starting with “3”, “5”, and “7” are listed in ascending order as they follow the earlier digits in numerical order: 3, 5, and 7.
Have a look on an example which contains a list of words.{educative, educated}
When we arrange these we get a list as a result containing the lexicographical order.{educated, educative}
Here’s how the transformation occurs:
- Both words start with the same sequence, “educat”.
- The next character in “educative” is “i”, while in “educated”, it’s “e”.
- “i” comes after “e” in the alphabetical order.
- Therefore, “educative” comes after “educated” because of the first differing character.
Code in C++ language to understand Lexicographically
#include <iostream>
using namespace std;
int find_min(int * arr, int size) {
//size must be greater than zero
int min = arr[0];
int temp = 0;
for(int i = 1; i < size; i++) {
temp = arr[i];
while (temp / 10 != 0) {
temp = temp / 10;
}
if (min > temp) {
min = temp;
}
}
return min;
}
int find_max(int * arr, int size) {
//size must be greater than zero
int max = arr[0];
for(int i = 1; i < size; i++) {
if (max < arr[i])
max = arr[i];
}
return max;
}
void should_print(int number, int toCompare){
int temp = number;
while (temp / 10 != 0) {
temp = temp / 10;
}
if(temp == toCompare) cout << number << " ";
}
void print_lexicographically(int * arr, int size) {
int min = find_min(arr, size);
int max = find_max(arr, size);
int k;
int val;
while (min <= max) {
for(int j = 0; j < size; j++){
should_print(arr[j], min);
}
min += 1;
}
}
int main() {
// your code goes here
int arr[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
print_lexicographically(arr, 10);
return 0;
}
Output :
11 13 17 19 2 23 29 3 5 7
In the above code there are four user defined function which are as follows :
- print_lexicographically() called with an array and the size of array as arguments.
- find_min() and find_max() functions find the minimum value, considering the leading digit of each element and maximum value in the array respectively.
- should_print() function checks if the leading digit of a number matches a given comparison digit and prints the number if there’s a match.