3 ms·
Binary digit strings are lexicographically sortable. These are the essence of computer representation of information. What's an example of a state space that l
by hgsgm 3y ago
Binary digit strings are lexicographically sortable. These are the essence of computer representation of information.
What's an example of a state space that lacks a lexicographically sortable representation?
Edit: in fact, "lexicographic" is an irrelevant detail in the blog post. It's just mentioned as a convenient way to define an ordering on the states. The sqrt(n) speedup is from having any ordering at all. As the article notes, mergesort relies on the same feature.
- reikonomusha 3y agoLexicographic ordering of the sets X and Y is crucial in the problem described in the post because it admits an efficient algorithm for iterating through X*Y without needing to enumerate them prior. It would not work for e.g. binary-on-disk ordering, since algebraic laws don't carry over in that ordering.