Krátká objednávka - Shortlex order
V matematice , a to zejména v teorii formálních jazyků , shortlex je celkové uspořádání pro konečné sekvence objektů, které samy o sobě mohou být zcela objednané. V pořadí shortlexu jsou sekvence primárně tříděny podle mohutnosti (délky) s nejkratšími sekvencemi jako první a sekvence stejné délky jsou tříděny do lexikografického pořadí . Shortlex uspořádání je také nazýván radix , délka-lexicographic , vojenské , nebo genealogický uspořádání.
V kontextu řetězců na zcela uspořádané abecedě je pořadí krátkého tisku totožné s lexikografickým řádem, kromě toho, že kratší řetězce předcházejí delší řetězce. Například pořadí shortlexů sady řetězců anglické abecedy (v obvyklém pořadí) je [ ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa , aab, aac, ..., zzz, ... ], kde ε označuje prázdný řetězec .
Řetězce v tomto pořadí přes pevnou konečnou abecedu lze umístit do korespondence zachování nezávazných celých čísel s nezápornými celými čísly , což dává bijektivní numerační systém pro reprezentaci čísel. Shortlexové řazení je také důležité v teorii automatických skupin .
Reference
 |
Tento článek týkající se algebry je útržek . Wikipedii můžete pomoci rozšířením . |