СВ в 13:07, 24 октября 2026

2026-10-24T13:07:41Z

← Предыдущая		Версия 13:07, 24 октября 2026
Строка 15:		Строка 15:
	$\widetilde x^k \prec_{lex} \widetilde y^k \Leftrightarrow \exists t\in\{1,...,k\}: x_i = y_i, i=\overline{1,t-1}, x_t\prec y_t$.		$\widetilde x^k \prec_{lex} \widetilde y^k \Leftrightarrow \exists t\in\{1,...,k\}: x_i = y_i, i=\overline{1,t-1}, x_t\prec y_t$.
	}}		}}

			[[Файл:p13-01-lexicographic-rule.svg\|frame\|none\|800px\|alt=Сравнение слов abc и acb по второй букве и слов ab и abc по правилу префикса\|Рис. 1. Слова сравниваются по первой различающейся букве: <math>b < c</math>, поэтому <math>abc < acb</math>. Если одно слово — начало другого, короткое идёт раньше: <math>ab < abc</math>.]]

	Выпишем все возможные перестановки чисел \{1, 2, 3, 4\}, выстроенные в лексикографическом порядке:		Выпишем все возможные перестановки чисел \{1, 2, 3, 4\}, выстроенные в лексикографическом порядке:

СВ в 19:14, 9 октября 2026

2026-10-09T19:14:20Z

← Предыдущая		Версия 19:14, 9 октября 2026
Строка 101:		Строка 101:

	Лексикографический и антилексикографический порядки являются отношениями строгого линейного порядка.		Лексикографический и антилексикографический порядки являются отношениями строгого линейного порядка.

			Конспект: [[Дискретная математика]]

СВ в 19:06, 9 октября 2026

2026-10-09T19:06:35Z

← Предыдущая		Версия 19:06, 9 октября 2026
Строка 46:		Строка 46:
	\end{array}		\end{array}
	</math>		</math>

	Заметим, что здесь мы привели только перестановки {{---}} последовательности из различных символов.		Заметим, что здесь мы привели только перестановки {{---}} последовательности из различных символов.
	Если мы захотим выписать все слова в данном алфавите, их окажется гораздо больше.		Если мы захотим выписать все слова в данном алфавите, их окажется гораздо больше.

СВ: Новая страница: «Лексикографический порядок {{---}} это порядок, в котором выстроены слова, например, в орфо...»

2026-10-09T19:06:06Z

Новая страница: «Лексикографический порядок {{---}} это порядок, в котором выстроены слова, например, в орфо...»

Новая страница

Лексикографический порядок {{---}} это порядок, в котором выстроены слова, например, в орфографических и русско-английских словарях.

Лексикографический порядок может быть введен на множестве слов (упорядоченных последовательностей элементов) над любым множеством, на котором уже введен строгий линейный порядок.

Пусть на множестве $X$ введен строгий линейный порядок $\prec$.
Введем отношение $\prec_{lex}$ на множестве $X^* = \{(x_1, x_2, ..., x_k) | k\in\mathbb{N}, x_i\in X\}$ всех слов над множеством $X$.
Пусть $\widetilde x^k = (x_1, ..., x_k)\in X^*$, $\widetilde y^l = (y_1, ..., y_l)\in X^*$, $\widetilde x^k\neq \widetilde y^l$ и $k\leq l$.

Будем говорить, что $\widetilde x^k \prec_{lex} \widetilde y^l$, если
1) существует такой индекс $t$, $1\leq t \leq k$, что $x_i = y_i$, $i=\overline{1,t-1}$, и $x_t\prec y_t$,
или 2) $k < l$ и $x_i = y_i$, $i=\overline{1,k}$. В противном случае $\widetilde y^l \prec_{lex} \widetilde x^k$.

{{Замечание
|content=На множестве слов одинаковой длины определение лексикографического порядка упростилось бы и приняло бы вид:
$\widetilde x^k \prec_{lex} \widetilde y^k \Leftrightarrow \exists t\in\{1,...,k\}: x_i = y_i, i=\overline{1,t-1}, x_t\prec y_t$.
}}

Выпишем все возможные перестановки чисел \{1, 2, 3, 4\}, выстроенные в лексикографическом порядке:

<math>
\begin{array}{c}
1 2 3 4\\
1 2 4 3\\
1 3 2 4\\
1 3 4 2\\
1 4 2 3\\
1 4 3 2\\
2 1 3 4\\
2 1 4 3\\
2 3 1 4\\
2 3 4 1\\
2 4 1 3\\
2 4 3 1\\
3 1 2 4\\
3 1 4 2\\
3 2 1 4\\
3 2 4 1\\
3 4 1 2\\
3 4 2 1\\
4 1 2 3\\
4 1 3 2\\
4 2 1 3\\
4 2 3 1\\
4 3 1 2\\
4 3 2 1\\
\end{array}
</math>
Заметим, что здесь мы привели только перестановки {{---}} последовательности из различных символов.
Если мы захотим выписать все слова в данном алфавите, их окажется гораздо больше.

Отметим также, что существует еще так называемый ''антилексикографический порядок''.
Он не является обратным лексикографическому порядку бинарным отношением.
Список всех перестановок $n$ чисел в антилексикографическом порядке может быть получен следующим образом: сначала нужно выстроить все такие перестановки
в лексикографическом порядке, а затем развернуть список в обратном порядке и развернуть каждое слово, описывающее перестановку.
Такой порядок может быть полезен, например, для словаря окончаний.

Используя те же обозначения и договоренности, что и при введении лексикографического порядка,
антилексикографический порядок можно определить следующим образом:
Будем говорить, что $\widetilde y^l \prec_{alex} \widetilde x^k$, если

1) существует такой индекс $t$, \mbox{$1\leq t \leq k$}, что $x_{k-i+1} = y_{l-i+1}$, $i=\overline{1,t-1}$ и $x_{k-t+1}\prec y_{l-t+1}$,

или 2) $k < l$ и $x_{k-i+1} = y_{l-i+1}$, $i=\overline{1,k}$. В противном случае $\widetilde y^l \prec_{alex} \widetilde x^k$.

{{Замечание
|content=На множестве слов одинаковой длины определение приняло бы следующий вид:
$\widetilde x^k \prec_{alex} \widetilde y^k \Leftrightarrow \exists t\in\{1,...,k\}: x_i = y_i, i=\overline{t+1,k}, y_t\prec x_t$.
}}

Приведем все возможные перестановки чисел $\{1, 2, 3, 4\}$, выстроенные в антилексикографическом порядке:

<math>
\begin{array}{c}
1 2 3 4\\
2 1 3 4\\
1 3 2 4\\
3 1 2 4\\
2 3 1 4\\
3 2 1 4\\
1 2 4 3\\
2 1 4 3\\
1 4 2 3\\
4 1 2 3\\
2 4 1 3\\
4 2 1 3\\
1 3 4 2\\
3 1 4 2\\
1 4 3 2\\
4 1 3 2\\
3 4 1 2\\
4 3 1 2\\
2 3 4 1\\
3 2 4 1\\
2 4 3 1\\
4 2 3 1\\
3 4 2 1\\
4 3 2 1\\
\end{array}
</math>

Лексикографический и антилексикографический порядки являются отношениями строгого линейного порядка.

Лексикографический порядок - История изменений

СВ в 13:07, 24 октября 2026

СВ в 19:14, 9 октября 2026

СВ в 19:06, 9 октября 2026

СВ: Новая страница: «Лексикографический порядок {{---}} это порядок, в котором выстроены слова, например, в орфо...»