Stack Overflow
Stack Overflow

Questions tagged [lexicographic]

lexicographic or lexicographical order is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters.

Definition:

Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as

(a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).

The result is a partial order. If A and B are totally ordered, then the result is a total order as well. More generally, one can define the lexicographic order on the Cartesian product of n ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.

Read more

238 questions
164
votes
7 answers

What is lexicographical order?

What is the exact meaning of lexicographical order? How it is different from alphabetical order?
NDesai
  • 1,741
  • 2
  • 12
  • 16
128
votes
6 answers

std::next_permutation Implementation Explanation

I was curious how std:next_permutation was implemented so I extracted the the gnu libstdc++ 4.7 version and sanitized the identifiers and formatting to produce the following demo... #include #include #include using…
Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
85
votes
8 answers

String Comparison in Java

What does "compare two strings lexicographically" mean?
Harshana
  • 7,297
  • 25
  • 99
  • 173
56
votes
8 answers

Template within template: why "`>>' should be `> >' within a nested template argument list"

I know that when we are using template inside another template, we should write it like this: vector > s; and if we write it without the whitespace: vector> s; we will get an error: `>>' should be `> >' within a nested…
zw324
  • 26,764
  • 16
  • 85
  • 118
42
votes
3 answers

Sort list of strings ignoring upper/lower case

I have a list which contains strings representing animal names. I need to sort the list. If I use sorted(list), it will give the list output with uppercase strings first and then lowercase. But I need the below output. Input: var =…
Darknight
  • 1,132
  • 2
  • 13
  • 31
24
votes
6 answers

operator< comparing multiple fields

I have the following operator< that is supposed to sort first by a value, then by another value: inline bool operator < (const obj& a, const obj& b) { if(a.field1< b.field1) return true; else return…
lezebulon
  • 7,607
  • 11
  • 42
  • 73
18
votes
12 answers

sort array of integers lexicographically C++

I want to sort a large array of integers (say 1 millon elements) lexicographically. Example: input [] = { 100, 21 , 22 , 99 , 1 , 927 } sorted[] = { 1 , 100, 21 , 22 , 927, 99 } I have done it using the simplest possible method: convert all…
Aseem Goyal
  • 2,683
  • 3
  • 31
  • 48
17
votes
5 answers

What's the simplest way of defining lexicographic comparison for elements of a class?

If I have a class that I want to be able to sort (ie support a less-than concept), and it has several data items such that I need to do lexicographic ordering then I need something like this: struct MyData { string surname; string forename; …
the_mandrill
  • 29,792
  • 6
  • 64
  • 93
15
votes
6 answers

How do I sort a collection of Lists in lexicographic order in Scala?

If A has the Ordered[A] trait, I'd like to be able to have code that works like this val collection: List[List[A]] = ... // construct a list of lists of As val sorted = collection sort { _ < _ } and get something where the lists have been sorted in…
Scott Morrison
  • 3,100
  • 24
  • 39
13
votes
4 answers

Lexicographic Order in Java

How is the lexicographic order defined in Java especially in reference to special characters like !, . and so on? An examplary order can be found here But how does Java define it's order? I ask because I'm sorting Strings on Java and on Oracle and…
oschrenk
  • 4,080
  • 4
  • 22
  • 25
12
votes
2 answers

How to find the lexicographically smallest string by reversing a substring?

I have a string S which consists of a's and b's. Perform the below operation once. Objective is to obtain the lexicographically smallest string. Operation: Reverse exactly one substring of S e.g. if S = abab then Output = aabb (reverse ba of…
cryptomanic
  • 5,986
  • 3
  • 18
  • 30
11
votes
8 answers

What is the shortest way in .NET to sort strings starting with 1, 10 and 2 and respect the number ordering?

I need to sort file names as follows: 1.log, 2.log, 10.log But when I use OrderBy(fn => fn) it will sort them as: 1.log, 10.log, 2.log I obviously know that this could be done by writing another comparer, but is there a simpler way to change from…
Erwin Mayer
  • 18,076
  • 9
  • 88
  • 126
11
votes
10 answers

Lexicographical sorting

I'm doing a problem that says "concatenate the words to generate the lexicographically lowest possible string." from a competition. Take for example this string: jibw ji jp bw jibw The actual output turns out to be: bw jibw jibw ji jp When I do…
Shawn Mclean
  • 56,733
  • 95
  • 279
  • 406
9
votes
4 answers

Most efficient way to calculate lexicographic index

Can anybody find any potentially more efficient algorithms for accomplishing the following task?: For any given permutation of the integers 0 thru 7, return the index which describes the permutation lexicographically (indexed from 0, not 1). For…
A Frayed Knot
  • 476
  • 5
  • 20
9
votes
2 answers

Find the lexicographic order of an integer partition

For permutations, given N and k, I have a function that finds the kth permutation of N in lexicographic order. Also, given a permutation perm, I have a function that finds the lexicographic index of the permutation among all permutations of N. To do…
Daniel
  • 944
  • 1
  • 7
  • 24
1
2 3
…
15 16