4 ms·
The generic algorithm he describes for significantly paring down and brute-forcing a permutation space is fascinating -- in particular, the insight that (in the
by TimTheTinker 3y ago
The generic algorithm he describes for significantly paring down and brute-forcing a permutation space is fascinating -- in particular, the insight that (in the worst case) only sqrt(N) iterations are needed to brute-force a permutation space when states in that space have lexicographically sortable representations.
I love the simplicity of using lexicographic sorting to solve a problem -- even sorting things like ISO-8601 date strings is delightful to me :-)
- pjc50 3y ago> in particular, the insight that (in the worst case) only sqrt(N) iterations are needed to brute-force a permutation space This is also the basis for "rainbow tables" for breaking password hashes.
- hgsgm 3y agoBinary 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.