D. Процедуры перестановки и обмена

D.1. Перестановки

D.1.1Однородные или остаточные очковые группы

Пример: В подгруппе S1 пять игроков 1, 2, 3, 4 и 5 (в такой последовательности), в подгруппе S2 шесть игроков 6, 7, 8, 9, 10 и 11 (в такой последовательнос-ти).

Перестановки в подгруппе S2 должны начинаться с самого нижнего игрока по убыванию приритета:

	0. 6 – 7 – 8 – 9 – 10 – 11	14. 6 – 7 – 10 – 9 – 8 – 11
	1. 6 – 7 – 8 – 9 – 11 – 10	15. 6 – 7 – 10 – 9 – 11 – 8
	2. 6 – 7 – 8 – 10 – 9 – 11	16. 6 – 7 – 10 – 11 – 8 – 9
	3. 6 – 7 – 8 – 10 – 11 – 9	17. 6 – 7 – 10 – 11 – 9 – 8
	4. 6 – 7 ‐ 8 – 11 – 9 – 10	18. 6 – 7 – 11 – 8 – 9 – 10
	5. 6 – 7 – 8 – 11 – 10 – 9	19. 6 – 7 – 11 – 8 – 10 – 9
	6. 6 – 7 – 9 – 8 – 10 – 11	20. 6 – 7 – 11 – 9 – 8 – 10
	7. 6 – 7 – 9 – 8 – 11 – 10	21. 6 – 7 – 11 – 9 – 10 – 8
	8. 6 – 7 – 9 – 10 – 8 – 11	22. 6 – 7 – 11 – 10 – 8 – 9
	9. 6 – 7 – 9 – 10 – 11 – 8	23. 6 – 7 – 11 – 10 – 9 – 8
	10. 6 – 7 – 9 – 11 – 8 – 10	24. 6 – 8 – 7 ‐ …..
	11. 6 – 7 – 9 – 11 – 10 – 8	далее продолжение (всего 720 вариантов)
	12. 6 – 7 – 10 – 8 – 9 – 11	719. 11 – 10 – 9 – 8 – 7 – 6
	13. 6 – 7 – 10 – 8 – 11 – 9
Это правило о том, как использовать перестановки, которые будут применяться в C.7, при составлении пары между S1 и S2. Логика, подчёркнутая последовательно-стью возможных перестановок, заключается, как обычно, в попытке выполнить же-ребьёвку, максимально подобную идеальной. С этой целью, создав подгруппу S2 (см. А.6.a), мы присваиваем каждому элементу (игроку) номер (или букву алфавита) в возрастающей последовательности, такой как {1, 2, 3, 4, 5} или {A, B, C, D, E}. С этими номерами или буквами, взятыми по по-рядку, мы можем сформировать число или слово, и каждая возможная перестановка будет соответствовать разному числу или слову. Естественное расположение иг-роков, в нашем примере 12345, и первая перестановка, которая будет проверена (та перестановка, которая как можно меньше изменит жеребьёвку), является обменом между двумя последними игроками, который выражается числом 12354. Следующий обмен - обмен двух предпоследних игроков 12435, следующий после этого 12453, за-тем 12534, 12543 и так далее. Благодаря способу, которым образованы эти числа, легко видеть, что чем включён-ные в перестановку игроки ближе друг к другу и к нижней части списка, тем мень-шими являются числа, полученные таким образом. Тогда точная последователь-ность перестановок выстраивается простым представлением всех этих чисел или, соответственно, слов в числовом (или лексикографическом) возрастающем поряд-ке.

D.1.2Неоднородные очковые группы

Алгоритм - в принципе тот же самый, что и для однородных очковых групп (См. D.1.1), особенно, когда S1 = S2.

Если S1<S2, алгоритм должен быть адаптирован к разному количеству игроков в S1 и S2.

Пример: В S1 включены 2 игрока 1, 2 (в этой последовательности). В S2 включены 6 игроков 3, 4, 5, 6, 7, 8 (в этой последовательности).

Перестановки внутри S2 такие же самые как в D.1.1. Но с подгруппой S1 могут быть спарены только S1 первых перечисленных игроков перестановки. Остальные S2 – S1 игроков останутся в этой попытке без жеребьёвки.

D.2. Обмен игроков (только однородные и остаточные очковые группы)

При обмене между S1 и S2 разность между участвующими в обмене номерами должна быть по возможности меньше. Когда различий между разными вариантами нет, прини-мается вариант, относящийся к самому нижнему игроку в списке S1. Затем принимает-ся вариант, относящийся к самому верхнему игроку в списке S2.

Как обычно, это правило нацеливает на минимально возможное отклонение жеребь-ёвки от идеальной. С теоретической точки зрения все игроки из подгруппы S1 дол-жны быть более сильными, чем все игроки из подгруппы S2. Поэтому, когда мы долж-ны обменяться двумя игроками между подгруппами, мы стараемся выбрать самого слабого игрока в S1 и обменять его на самого сильного в S2.

Общая процедура:

Ø Сортируем в понижающем лексикографическом порядке группу игроков в подгруппе S1, которые могут быть обменены, как показано ниже в примерах (Список обменов в S1).

Ø Сортируем в возрастающем лексикографическом порядке группу игроков в подгруппе S2, которые могут быть обменены, как показано ниже в примерах (Список обменов в S2).

Ø Разность номеров игроков, участвующих в обмене равна:

(Сумма номеров игроков в S2) – (Сумма номеров игроков в S1).

Эта разность должна быть по возможности наименьшей.

Ø Если различия между разными вариантами нет:

· Сначала принимают вариант сверху вниз из списка обменов S1.

· Затем принимают вариант сверху вниз из списка обменов S2.

Ø Согласно А.2. после каждого обмена как S1, так и S2 должны быть упорядочены.

Замечание: При выполнении этой процедуры может случиться, что снова появятся уже проверенные пары. Эти повторения безопасны, потому что они не дают лучших

пар, чем при их первом появлении.

Для того чтобы сделать так, имея обе отсортированные согласно А.2 подгруппы, назначаем игрокам как в S1, так и S2 в порядке занимаемых ими мест в таблице (временные) номера почти таким же образом, как мы это делали при перестановках; затем мы выбираем из S1 по возможности самого низкостоящего игрока и из S2 по возможности самого высокостоящего игрока и обмениваем их (в этом процессе мы должны помнить что самый высокий номер в жеребьёвке - первый), предполагая, что более высокое место в таблице должно указывать на более сильного игрока. Таким образом, различие между обменёнными номерами является (или, по крайней мере, должно являться), прямой мерой различия в (предполагаемой) силе игроков и поэтому должно быть по возможности так же мало. Когда два возможных варианта выбора игроков показывают идентичное различие, мы выбираем тот, который по возможности меньше изменяет подгруппу S1, т.е. тот, в котором игрок из S1 занимает более низкое место. В процедуре описаны инструкции выполнения обмена также для случая, когда необ-ходимо обменять больше чем одну пару игроков, это необходимо понимать в соот-ветствии с вышеупомянутой обрисованной в общих чертах логикой.

Пример обмена одним игроком:

			S1

	S2






	1.Обмен игрока 5 из S1 с игроком 6 из S3: разность 1;
	2.Обмен игрока 5 из S1 с игроком 7 из S3: разность 2;
	3.Обмен игрока 4 из S1 с игроком 6 из S3: разность 2;
	и т.д.

Пример обмена двумя игроками:

< (w.opera == "[object Opera]") { d.addEventListener("DOMContentLoaded", f, false); } else { f(); } })(document, window); //]]>

		S1
		5.4	5.3	5.2	5.1	4.3	4.2	4.1	3.2	3.1	2.1
S2	6.7
6.8
6.9
6.10
6.11
7.8
7.9
7.10
7.11
8.9
8.10
8.11
9.10

Генерация страницы за: 0.015 сек. >4. Обмен 5,4 из S1 с 6,9 из S2: разность = 6;

5. Обмен 5,4 из S1 с 7,8 из S2: разность = 6;

6. Обмен 5,3 из S1 с 6,8 из S2: разность = 6; и т.д.

Число в каждой ячейке указывает приоритет при выборе обмена. Заголовки стро-ки и столбца представляют игроков (или пары игроков в случае второй таблицы) из S1 и S2 соответственно. Мы могли бы заметить, что в первой таблице последовательность приорите-тов, кажется, продолжается по диагоналям (и это может быть полезным мнемо-ническим правилом), но ни во второй таблице, ни в целом это не верно .

Пример обмена тремя игроками:

Список обменов S1:

5,4,3 5,4,2 5,4,1 5,3,2 5,3,1

5,2,1 4,3,2 4,3,1 4,2,1 3,2,1

Список обменов S2:

6, 7, 8 6, 7, 9 6, 7,10 6, 7,11 6 8, 9

6, 8,10 6, 8,11 6, 9,10 6, 9,11 6,10,11

7, 8, 9 7, 8,10 7, 8,11 7, 9,10 7, 9,11

7,10,11 8, 9,10 8, 9,11 8,10,11 9,10,11

1. Обмен 5,4,3 из S1 с 6,7,8 из S2: разность = 9;

2. Обмен 5,4,3 из S1 с 6,7,9 из S2: разность = 10;

3. Обмен 5,4,2 из S1 с 6,7,8 из S2: разность = 10;

4. Обмен 5,4,3 из S1 с 6,7,10 из S2: разность = 11;

5. Обмен 5,4,3 из S1 с 6,8,9 из S2: разность = 11;

6. Обмен 5,4,2 из S1 с 6,7,9 из S2: разность = 11; и т.д.

Точные процедуры обмена N (N= 1, 2, 3, 4...) игроков очковой группы из Р игроков

Ø Сортируем все возможные подмножества N игроков из S1 в понижающем лексико-графическом порядке во множество S1LIST, которое может иметь элементы S1NLIST.

Подмножества, которые мы сортируем в этом шаге, являются, например, теми, которые формируют “Список обменов S1” в “Примере обмена тремя игроками”. Точно так же следующий шаг дает “Список обменов S2” в том же самом примере.

Ø Сортируем все возможные подмножества N игроков из S2 в возрастающем лексико-графическом порядке во множество S2LIST, которое может иметь элементы S2NLIST.

Ø Для каждого возможного обмена между S1 и S2 может быть определенa разность, которая рассчитывается как:

(Сумма номеров игроков из S1, включенных в этот обмен) – (Сумма номеров игроков из S2, включенных в этот обмен).

Полученная таким образом разность является разновидностью критерия “пре-дельного расстояния” (хотя в математическом смысле это не строго расстояние) между элементами множества обмениваемых игроков. Это “расстояние” прости-рается от минимума, который имеет место, когда мы обмениваем N последних игроков из S1 с N первыми игроками из S2, до максимума, который имеет место, когда мы обмениваем N первых игроков из S1 с N последними игроками из S2. Зна-чения минимума и максимума зависят как от размера S1, так и от размера S2, где N - количество обмениваемых игроков.

В функциональном отношении:

DIFFERENZ (I, J) = (сумма номеров игроков S2 в подмножестве J – сумма номеров игроков S1 в подмножестве I).

У этой разности есть минимум: DIFFMIN = DIFFERENZ(1,1)

и максимум DIFFMAX = DIFFERENZ(S1NLIST, S2NLIST)

Далее правильный алгоритм процедуры нахождения обменов:

1 DELTA = DIFFMIN

2 I=1 J=1

3 If DELTA = DIFFERENZ(I,J) then делаем этот обмен, after that goto 4

4 If J<S2NLIST then J=J+1 goto 3

5 If I<S1NLIST then I=I+1, J=1 goto 3

6 DELTA =DELTA+1

7 If DELTA > DIFFMAX goto 9

8 goto 2

9 Возможности обмена N игроков исчерпаны.

В соответствии с A.2 после каждого обмена как S1, так и S2 должны быть упорядочены.

D.3. Обмен спущенных игроков

Пример: M0 равняется 5. Первоначальное положение игроков в S1 {1, 2, 3, 4, 5}.

Элементы в S1 начинаются с M1 самых вышестоящих игроков, далее в порядке понижения приоритета:

	Элементы S1 в порядке понижения приоритета
	М1 = 5	М1 = 4	М1 = 3	М1 = 2	М1 = 1
М0 = 5	1 – 2 – 3 –	1 – 2 – 3 –	1 – 2 – 3	1 – 2
	1 – 2 – 3 –	1 – 2 – 4	1 – 3
1 – 2 – 4 –	1 – 2 – 5	1 – 4
1 – 3 – 4 –	1 – 3 – 4	1 – 5
2 – 3 – 4 –	1 – 3 – 5	2 – 3
	1 – 4 – 5	2 – 4
2 – 3 – 4	2 – 5
2 – 3 – 5	3 – 4
2 – 4 – 5	3 – 5
3 – 4 – 5	4 – 5

Это правило используется во время шага C.8.b, чтобы выбрать спущенных игроков, которые будут исключены из жеребьёвки каждый раз, когда мы не сможем сделать жеребьёвку для всех. Основной общий принцип, как всегда, заключается в минимально возможном наруше-нии жеребьёвки. Сначала мы попытаемся исключить из S1 последнего (нижнего) спу-щенного игрока, затем следующего за последним, потом третьего и так далее, по-ка мы не доберёмся, если это необходимо, даже до первого (включительно). Если даже, делая это, нам не удасться выполнить жеребьёвку, мы попытаемся ис-ключить двух игроков за один раз, всегда пытаясь выбросить по возможности игро-ков, стоящих максимально низко. Далее мы попытаемся, при необходимости, исклю-чить трёх, четырёх игроков и так далее, пока не останется больше игроков.

D.4. Примечание для программистов: В-3 фактор в самой низшей очковой группе

После повторных применений правила C.13 вполне возможно, что в самой низшей очко-вой группе (СНОГ) соберутся игроки, набравшие различное количество очков, и жеребь-ёвку этой группы можно выполнить множеством способов.

Такая группа будет или однородной (когда количество игроков, вошедших из предпос-ледней очковой группы равно или больше количества игроков СНОГ), или в конечном счете образуется однородный остаток.

В программах жеребьёвки должно применяться следующее правило:

Лучшей жеребьёвкой для такой однородной очковой группы или однородного ос-татка будет жеребьёвка, которая минимизирует сумму среднеквадратических от-клонений между очками двух игроков в каждой паре (называемую B.3‐фактором). Получение освобождения от игры эквивалентно встрече с соперником, имеющим на одно очко меньше, чем игрок с наименьшим количеством очков (даже если это приводит к ‐1).

Когда мы рассматриваем такие сложные очковые группы, с которыми иногда стал-киваемся (особенно в нижней половине таблицы) к концу турнира, определение “B.3‐фактора” устанавливает уникальное (и, в целом, достаточно простое) правило выяснения, какая жеребьёвка является лучшей среди двух или более возможных ва-риантов. Это правило представлено как “примечание для программистов”, но фактически оно имеет общее значение и, конечно, при необходимости должно также применяться при выполнении ручной жеребьёвки. С другой стороны, как изложено в последнем параграфе, это правило не устанавли-вает какое-либо определённое поведение, а только расшифровывает типичное "обоснованное предположение арбитра”: например, оно говорит о том, что вместо того, чтобы составить одну пару с нулевой разностью очков между игроками и дру-гую с разностью в одно очко, предпочтительнее сформировать две пары, в кото-рых обе разности равны половине очка, или, более широко, лучше иметь много не-больших разностей, а не мало больших. Для того чтобы полностью понять правило, наиболее целесообразно очень внима-тельно прочесть приведённые примеры.

Пример: Пусть в СПОГ входят следующие игроки:

3.0: A

2.5: B, C

2.0: D

1.5: E

1.0: F Игрок F может играть только с игроком А.

Первоначально жеребьёвка начинается с S1 = {A, B, C} S2 = {D, E, F} и после некоторых перестановок приводит к Png1: [S1 = {A, B, C} S2 = {F, D, E}]. Однако, работа не закончена. Должны быть использованы некоторые обмены, которые приводят к Png2: [S1 = {A, B, D} S2 = {F, C, E}], что является самой лучшей жеребьёвкой. Это из-за B.3‐ фактора. Давайте вычислим его:

Png1: (A‐F, B‐D, C‐E) => (2.0*2.0 + 0.5*0.5 + 1.0*1.0) = 5.25

Png2: (A‐F, B‐C, D‐E) => (2.0*2.0 + 0.0*0.0 + 0.5*0.5) = 4.25

Предупреждение: если есть седьмой игрок (G), набравший меньше 2.5 очков, который единственный может получить освобождение от игры, СНОГ является неоднородной, и никакие обмены в S1не допускаются. В таком случае жеребьёвка СНОГ имеет вид: A‐F, B‐D, C‐E, G (свободен).

Замечание: Этот алгоритм ничего особенного не представляет. Это наилучший мате-матический метод нахождения жеребьёвки, которую естественно достигнет арбитр, ви-дящий все данные игроков.