генерация таблицы игр чемпионата

[krinart]

luitzen
спасибо большое... оказывается всё намного проще наверное придётся воспользоваться этим вариантом, но всётаки коданибудь я напишу свой, который будет действительно "случайным", ведь этот вариант по сути является псевдо-случайным

[Nikita_from_SPb]

krinart
родилась такая мысль еще. Можно сделать неслучайную таблицу $ N \times N$, а потом сделать случайную перестановку команд. То есть была, скажем, для N=4,
0123
1032
2301
3210
и случайная перестановка (3, 1, 4, 2)
и воспринимаем так:
3 | 1 | 4 | 2
------------
3|0 1 2 3
1|1 0 3 2
4|2 3 0 1
2|3 2 1 0

[krinart]

а каким образом формируется эта неслучайная таблица? ведь у меня ж будет не только 4 команды, а например 16 или 20... тогда нужен алгоритм создания этой таблицы, а у меня чтото пока не получается его придумать

[маткиб]

Неслучайные туры можно сгенерировать например так.
Пусть N=2M. Команды нумеруем от 0 до N-1. A<->B означает "A играет с B".

Первые M-1 туров.
i-й тур (1<=i<=M-1): j<->M+(j+i) mod M, j=0,1,...,M-1

Остальные M туров. Возможны 2 случая.

1) M=2K+1.
Тогда i-й тур (0<=i<=M-1): (i-j) mod M<->(i+j) mod M, M+(i-j) mod M<->M+(i+j) mod M, j=1,2,...,K,
i<->i+M

2) M=2K.
Тогда эти оставшиеся туры делятся ещё на 2 группы.
2A) K туров. i-й тур (0<=i<=K-1): (i-j) mod M<->(i+j+1) mod M, M+(i-j) mod M<->M+(i+j+1) mod M, j = 0,1,....,K-1.
2Б) K туров. i-й тур (0<=i<=K-1): (i-j) mod M<->(i+j) mod M, M+(i-j) mod M<->M+(i+j) mod M, j=1,...,K-1,
i<->i+M, (i+k) mod M<->M+(i+k) mod M.

[нг]

Переношу в Computer Science

[krinart]

прошу прощения за временное молчание...

маткиб, спасибо за идею... а можно это всё несколько проще записать? во-первых у тебя странная индексация, мы везде считали команды от 1 до N, у тебя же начинатеся с 0... во-вторых весьма странная запись "M+(j+i) mod M" что есть тоже самое что и "(j+i) mod M", либо нужно правильно расставить скобки..

вобще было бы хорошо, если бы ты написал идею этого алгоритма, чтобы я смог разобраться.... заранее спасибо

[маткиб]

Индексация от 0, потому что удобно (остатки от деления обычно считают от нуля).

mod я использую как в паскале, т.е. это операция вычисления остатка от деления, её приоритет выше, чем у сложения. Единственное отличие от паскаля - я полагаю, что остаток от деления x на положительное число y всегда между 0 и y-1 (даже если x отрицательное).

Идею будет конечно трудно объяснить, проще посмотреть, что получится на конкретном примере типа N=10. Есть очень простая идея - разбить окружность на N равных частей и расставить точки (игроков) в узлах разбиения, потом относить к одному турниру пары команд, для которых прямые, соединяющие соответствующие им точки, параллельны. На основе этого получается нечто похожее на ту матрицу, которую я написал в самом начале. Но эта идея неверна, потому что так не во всех турнирах участвуют все команды.

А то, что я написал - это модификация этой идеи. Нужно сделать 2 одинаковые окружности - в первой равномерно расставить команды от 0 до M-1, во второй - от M до 2M-1, а дальше объяснить трудно, проще реально рассмотреть N=10 и N=12 (нарисовать на бумажке).