748
правок
Изменения
→Псевдокод
{{Задача
|definition = Дана {{Acronym | перестановка | на самом деле может быть и мультиперестановкой }} <tex>\pi</tex> множества <tex>~\{1, 2,~\dots,~n\}</tex> Найти . Требуется найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> - — длина НВП.
}}
[[Файл:Task.jpg]]== Алгоритм <tex>за O(n\operatorname{log}\operatorname{log}n)</tex> ==
=== Нахождение длины НВП ===
==== Основная идея ====
Пусть <tex>\pi(n){\pi_1,\pi_2,~\dots,~\pi_n\}</tex> - — входная перестановка.
==== Пример ====
''' Типы операций''' * Добавление элемента, который больше всех предыдущих: [[Файл:Operation1.jpg]] * Замещение элемента более подходящим, т.е. добавление немаксимального элемента:
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex> || <tex>\pi_{10}</tex> || <tex>\pi_{11}</tex> || <tex>\pi_{12}</tex>
|-align="center"
| <tex>9 </tex> || 2 <tex>3</tex> || <tex>10</tex> || <tex>4</tex> || <tex>8</tex> || <tex>1 </tex> || 3 <tex>2</tex> || 7 <tex>12</tex> || 5 <tex>6</tex> || 6 <tex>5</tex> || 8 <tex>7</tex> || 4 <tex>11</tex>
|}
''' Состояние очереди при каждом добавлении:'''
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| style="background:#FFCC00FFCFCF"| <tex>9 </tex> || || || || || style="background:#9886ffCFCFFF"|<tex>9</tex>|-align="center" | style="background:#FFCFCF"| <tex>3</tex> || || || || || style="background: #CFCFFF"| <tex>3</tex>|-align="center" | <tex>3</tex> || style="background:#FFCFCF"| <tex>10</tex> || || || || style="background: #CFCFFF"| <tex>10</tex>|-align="center" | <tex>3</tex> || style="background:#FFCFCF"| <tex>4</tex> || || || || style="background: #CFCFFF"| <tex>4</tex>
|-align="center"
| <tex>3</tex> || <tex>4</tex> || style="background:#FFCC00FFCFCF"| 2 || || <tex>8</tex> || || || style="background:#9886ffCFCFFF"|2<tex>8</tex>
|-align="center"
| style="background:#FFCC00FFCFCF"| <tex>1 </tex> || <tex>4</tex> || <tex>8</tex> || || || style="background:#9886ffCFCFFF"|<tex>1</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFCFCF"| 3 <tex>2</tex> || <tex>8</tex> || || || style="background:#9886ffCFCFFF"|3<tex>2</tex>
|-align="center"
| <tex>1 </tex> || 3 <tex>2</tex> || <tex>8</tex> || style="background:#FFCC00FFCFCF"| 7 || <tex>12</tex> || || style="background:#9886ffCFCFFF"|7<tex>12</tex>
|-align="center"
| <tex>1 </tex> || 3 <tex>2</tex> || style="background:#FFCC00FFCFCF"| 5 <tex>6</tex> || <tex>12</tex> || || style="background:#9886ffCFCFFF"|5<tex>6</tex>
|-align="center"
| <tex>1 </tex> || 3 || 5 <tex>2</tex> || style="background:#FFCC00FFCFCF"| 6 <tex>5</tex> || <tex>12</tex> || || style="background:#9886ffCFCFFF"|6<tex>5</tex>
|-align="center"
| <tex>1 </tex> || 3 <tex>2</tex> || <tex>5 || 6 </tex> || style="background:#FFCC00FFCFCF"| 8 <tex>7</tex> || || style="background:#9886ffCFCFFF"|8<tex>7</tex>
|-align="center"
| <tex>1 </tex> || 3 <tex>2</tex> || <tex>5</tex> || <tex>7</tex> || style="background:#FFCC00FFCFCF"| 4 || 6 || 8 <tex>11</tex> || style="background:#9886ffCFCFFF"|4<tex>11</tex>
|}
==== Псевдокод ====
==== Основная идея ====
Будем запоминать пары: для каждого элемента записываем его "предшественника".
Тогда, выбрав какой-нибудь лучший элемент для максимальной длиныпройдя по предшественникам, начиная с последнего элемента очереди <tex>B</tex>, мы можем легко восстановить все НВП.==== Общий вид алгоритма ===={| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"|-align="center"! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>|-align="center" | <tex>9</tex> || || || || || style="background: #CFCFFF"| <tex>9</tex>|-align="center" | <tex>3</tex> || || || || || style="background: #CFCFFF"| <tex>3</tex>|-align="center" | <tex>3</tex> || <tex>10</tex> || || || || style="background: #CFCFFF"| <tex>10</tex>|-align="center" | <tex>3</tex> || <tex>4</tex> || || || || style="background: #CFCFFF"| <tex>4</tex>|-align="center" | <tex>3</tex> || <tex>4</tex> || <tex>8</tex> || || || style="background: #CFCFFF"| <tex>8</tex>|-align="center" | style="background:#FFDF90"| <tex>1</tex> || <tex>4</tex> || <tex>8</tex> || || || style="background: #CFCFFF"| <tex>1</tex>|-align="center" | style="background:#FFCFCF"| <tex>1</tex> || style="background:#FFDF90"| <tex>2</tex> || <tex>8</tex> || || || style="background: #CFCFFF"| <tex>2</tex>|-align="center" | <tex>1</tex> || style="background:#FFDF90"| <tex>2</tex> || <tex>8</tex> || <tex>12</tex> || || style="background: #CFCFFF"| <tex>12</tex>|-align="center" | <tex>1</tex> || style="background:#FFDF90"| <tex>2</tex> || <tex>6</tex> || <tex>12</tex> || || style="background: #CFCFFF"| <tex>6</tex>|-align="center" | <tex>1</tex> || style="background:#FFCFCF"| <tex>2</tex> || style="background:#FFDF90"| <tex>5</tex> || <tex>12</tex> || || style="background: #CFCFFF"| <tex>5</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || style="background:#FFCFCF"| <tex>5</tex> || style="background:#FFDF90"| <tex>7</tex> || || style="background: #CFCFFF"| <tex>7</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || <tex>5</tex> || style="background:#FFCFCF"| <tex>7</tex> || style="background:#FFCFCF"| <tex>11</tex> || style="background: #CFCFFF"| <tex>11</tex>|} {| class="wikitable" style="color: black; background-color:#ffffcc;" cellpadding="10"|-align="center"! colspan="12" | predecessor|-align="center"! <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || <tex>5</tex> || <tex>6</tex> || <tex>7</tex> || <tex>8</tex> || <tex>9</tex> || <tex>10</tex> || <tex>11</tex> || <tex>12</tex> |-align="center"| || <tex>1</tex> || || <tex>3</tex> || <tex>2</tex> || <tex>2</tex> || <tex>5</tex> || <tex>4</tex> || || <tex>3</tex> || <tex>7</tex> || <tex>8</tex>|}
==== Псевдокод ====