Krótkie zamówienie - Shortlex order
W matematyce , a szczególnie w teorii języków formalnych , shortlex jest całkowite uporządkowanie dla ciągów skończonych obiektów, które same mogą być całkowicie zamawianych. W uporządkowaniu skróconym sekwencje są sortowane przede wszystkim według liczności (długości), przy czym najpierw są najkrótsze, a sekwencje o tej samej długości są sortowane w porządku leksykograficznym . Porządkowanie shortlex jest również nazywane porządkiem radix , porządkiem leksykograficznym , wojskowym lub genealogicznym .
W kontekście łańcuchów w całkowicie uporządkowanym alfabecie, kolejność krótkich znaków jest identyczna z porządkiem leksykograficznym, z tym wyjątkiem, że krótsze ciągi poprzedzają dłuższe. Na przykład krótka kolejność zbioru ciągów w alfabecie angielskim (w zwykłej kolejności) to [ ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa , aab, aac, ..., zzz, ... ], gdzie ε oznacza pusty ciąg .
Łańcuchy w tej kolejności w ustalonym alfabecie skończonym można umieścić w zachowującej porządek korespondencji jeden do jednego z nieujemnymi liczbami całkowitymi , dając bijektywny system numeracji do reprezentowania liczb. Porządkowanie skrótów jest również ważne w teorii grup automatycznych .
Bibliografia
 |
Ten artykuł związany z algebrą jest skrótem . Możesz pomóc Wikipedii, rozbudowując ją . |