1
$\begingroup$

This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/

Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Examples:

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa" 
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'

Notice that the solution calls for comparison of adjacent word-pairs only, when discovering new edges. It is unnecessary to add edges from comparing non-adjacent words. This seems straightforward and intuitive to me, but how do we prove it?

An edge-discovery is done by comparing two strings, iterating through their characters, and finding the first pair of characters which differ. The former string's character precedes the latter string's character. In the case of the former string being a substring of the latter, then the edge discovery fails to return a pair. (It's impossible for the latter string to be a substring of the former)

Given a directed acyclic graph built from pairwise edge-discoveries of adjacent pairs <word[1], word[2]>, <word[2], word[3]>, ..., <word[n-1], word[n]>. Prove that comparing any two words which are not adjacent will not yield any new information, i.e. the edge-ordering discovered by the new comparison will already have been present, or implied by transitivity of edge-orderings in the existing graph.

Edit to add: I have a prefix-tree-based proof, but I'm no good at writing proofs and would welcome better-written proofs.

$\endgroup$
5
  • $\begingroup$ "I have a prefix-tree-based proof". I would believe a directed-acyclic-graph based proof would be more plausible. $\endgroup$
    – John L.
    Oct 16, 2018 at 17:06
  • $\begingroup$ It's not so much a proof rather than a diagram that will convince your average programmer that it is true :-) Mostly rests on the claim that single-character cases (same shared-prefix-length) are transitive, and across "boundaries" (depth-levels of the prefix-tree), we only need to apply transitivity across each adjacent leaf node. Like I said, if I wrote this it would be a pretty bad proof... $\endgroup$
    – Anton
    Oct 17, 2018 at 1:33
  • $\begingroup$ Well, your proof might be similar to my first attempt as well. Not necessarily rigorous enough, but convincing enough for someone not very critical. Or at least to convince myself initially. $\endgroup$
    – John L.
    Oct 17, 2018 at 1:37
  • $\begingroup$ I'm reading your current answer, and thanks for writing it! $\endgroup$
    – Anton
    Oct 17, 2018 at 1:39
  • $\begingroup$ Welcome! As I have said, your question is so well written that I just copied and pasted here and there. This does not happen very often, as you may see from some of my even longer answer to some other questions, where I almost restated the whole problem. I could say I am on the rather picky side. $\endgroup$
    – John L.
    Oct 17, 2018 at 1:44

2 Answers 2

1
$\begingroup$

Thanks to your very well-written question, which makes my answer writing a real pleasure.

Claim I: "it is unnecessary to add edges from comparing non-adjacent words."

Let us take a look at how the algorithm pulls information when comparing two words, which is "iterating through their characters, and finding the first pair of characters which differ". Then it obtains the requirement "the former string's character precedes the latter string's character". Use $R_{i,j}$ to denote the requirement thus obtained from two words word[i] and word[j]. In term of binary relation, $R_{i,j}$ can be expressed in the form $\alpha<\beta$ for some character $\alpha, \beta$. Note $R_{i,j}$, if satisfied, determines word[i] and word[j] must be arranged in the given order as in the array word. In other words, any strict partial order on the characters that includes $R_{i,j}$ must sort word[i] and word[j] in the order as given in the array word.

Let $O$ be the minimum strict partial order on the characters that includes $R_{1,2}, R_{2,3}, \cdots, R_{n-1,n}$. Then any arrangement of words must put word[2] after word[1], word[3] after word[2], ..., word[n] after word[n-1] if that arrangement is in accordance with $O$. That is, all words must be arranged in the order exactly as given in the array word. Since any desired dictionary order, a.k.a. lexicographic order, (which can be obtained by a topological sort according to those n-1 requirements), is a strict total order (and hence also a strict partial order) that extends $O$, no more information is needed to order any pair of words.

Claim I is proved in the sense of the last statement.


Lemma: Let $<_1$ be a strict partial order on a set $S$ and $a,b\in S$. If $a\not<_1b$, (which does not implies $b<_1 a$), then there is a strict partial order $<_2$ on $S$ that extends $<_1$ with $b<_2 a$.

The lemma says that if one element is not defined as smaller than another element in a strict partial order, then we can assign the relationship between those two elements the other way around without causing conflict. It will be clear soon that this lemma is the crux of this answer.

In case that you are not familiar with the terminologies of partial order, here is an equivalent version in term of directed graph. Given a directed acyclic graph whose transitive closure has no edge going from one particular vertex to another vertex, if you add an edge that goes from the latter vertex to the former vertex, the resulting graph will still be acyclic. (One can also note that whether a directed graph is acyclic or not will not be changed if we take a transitive closure of the graph. This transitive closure corresponds to the transitivity of the strict partial order.)

I will leave the simple proof of this lemma to you.


Claim II: "Comparing any two words which are not adjacent will not yield any new information."

Let us continue to use the terms introduced in the proof of Claim I. Before we proceed to a proof, let us define what is existing information. The existing information is all requirements $R_{i,i+1}$ for $1\le i\le n-1$ or, what is equivalent, $O$, the minimum strict partial order which includes those requirements (and their implications), which is able to determine the order relationship of any pair of words in the array word.

For the sake of contradiction, suppose comparing word[i] and word[j] could yield a requirement that can be considered as new information, i.e., assuming this new requirement is $\alpha'<\beta'$ for some character $\alpha', \beta'$, that relationship between $\alpha'$ and $\beta'$ is not in $O$. By the above lemma, we can extends $O$ with $\beta'<\alpha'$ to obtain another strict partial order $O'$. Note that $O'$ requires word[i] and word[j] be arranged in the reverse order of how it appears in array word, which contradicts our conclusion above that any strict partial order that extends $O$ must put word[i] and word[j] in the same order as it appears in array word.

Claim II is proved.


For an even higher level of rigor, we should also note explicitly what happens when two words, one of which is a prefix of the other one, are compared. We should also mention explicitly the case when the initial array word is not consistent, such as ['a', 'b', 'a']. We should flesh out more details about the strict partial orders. I will not go into such detail, assuming the above explanation is enough to enable readers who are able to read thus far to fill in the details if needed.

$\endgroup$
7
  • $\begingroup$ @Anton, I just did a few attempts to make my exposition more accurate and easier to understand. Another simplification could be replacing "strict partial order" with "partial order". Well, you may read the whole answer ignoring "strict". Does my answer make sense to you? $\endgroup$
    – John L.
    Oct 16, 2018 at 21:20
  • $\begingroup$ Thanks for this answer. I agree with you, although I think this part isn't obvious: "Note that O′ requires word[i] and word[j] be arranged in the reverse order of how it appears in array word, which contradicts our conclusion above that any strict partial order that extends O must put word[i] and word[j] in the same order as it appears in array word." $\endgroup$
    – Anton
    Oct 17, 2018 at 2:02
  • $\begingroup$ Intuitively makes perfect sense though: it's really not possible, after pairwise comparisons, to have "missed out" on an edge, such that you have a DAG with disconnected components. Any DAG built from a dictionary containing letters a...z must be weakly connected. $\endgroup$
    – Anton
    Oct 17, 2018 at 2:04
  • $\begingroup$ I thought that part was too obvious. $\alpha'<\beta'$ is obtained by comparing word[i] and word[j]. That is, skipping the same prefix, the word at front has $\alpha'$ and the word at behind has $\beta'$. Now that $O'$ includes $\beta'<\alpha'$, of course, it will arrange those two words in reverse order. In fact, it seems hard for me to see your "intuitively ... perfect sense". I do not know why "Any DAG built from a dictionary containing letters a...z must be weakly connected". Does it apply when the word is, for example, ['alice', 'bob']? $\endgroup$
    – John L.
    Oct 17, 2018 at 3:14
  • $\begingroup$ it's really not possible, after pairwise comparisons, to have "missed out" on an edge. It looks like I should prove that that dictionary order is a total order (although it is sort of obvious and has been assumed in various problems). That is reason why once we have $R_{1,2}, R_{2,3}, \cdots, R_{n-1,n}$ in the dictionary order, that dictionary order will not missed out on an edge. $\endgroup$
    – John L.
    Oct 17, 2018 at 3:19
1
$\begingroup$

Let's denote the words by $w[1],\ldots,w[n]$. Suppose that $i < j$ and that $w[i],w[j]$ first differ on the $t$th coordinate. In symbols, $w[i]_{<t} = w[j]_{<t}$ but $w[i]_t < w[j]_t$ (I hope the notation is obvious).

I first claim that $w[k]_{<t} = w[k+1]_{<t}$ for all $k \in \{i,\ldots,j-1\}$. Indeed, suppose that $w[k]_{<t} < w[k+1]_{<t}$ for some $k \in \{i,\ldots,j-1\}$. Then $w[i]_{<t} \leq w[k]_{<t} < w[k+1]_{<t} \leq w[j]_{<t}$, contradicting the assumption $w[i]_{<t} = w[j]_{<t}$.

Call an index $k \in \{i,\ldots,j-1\}$ special if $w[k]_t < w[k+1]_t$. Let the special indices be $k_1,\ldots,k_m$. Then $$ w[i]_t = w[k_1]_t < w[k_1+1]_t = w[k_2]_t < w[k_2+1]_t \cdots w[k_m]_t < w[k_m+1]_t = w[j]_t. $$ This shows that $w[i]_t < w[j]_t$ follows from $w[k_1]_t < w[k_1+1]_t,\ldots,w[k_m]_t < w[k_m+1]_t$ by transitivity. (Here we are using the fact, proved earlier, that $w[k_r]_{<t} = w[k_r+1]_{<t}$ for $r \in \{1,\ldots,t\}$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.