krinart
Новичок
|
    
здраствуйте...
помогите пожалуста с решнием одной задачки... мне нужно составить таблицу игр чемпионата для n команд, таким образом, чтобы строки это были туры, а столбцы команды...
например, может получиться такая таблица
1 2 3 4 5 6
------------------
1 | 2 1 6 5 4 3
2 | 3 5 1 6 2 4
3 | 6 4 5 2 3 1
4 | 4 3 2 1 6 5
5 | 5 6 4 3 1 2
то есть в результате каждая команда сыграет с каждой по одному разу...
на самом деле вся задача сводится к построению матрицы размером (N-1)*N таким образом, чтобы числа в столбцах и строках не повторялись, а-ля магический квадрат, но плюс к этому, добавляется ещё одно условие - каждому элементу k, находящемуся на позиции [i, j] должен соответствовать элемент j, находящийся на позиции [i, k], чтобы каманды "играли друг с другом" в каждом туре..
я написал алгоритм, который действует следующим образом:
1. обнуляем матрицу
2. проходим всю матрицу по строкам
3. если элемент [i, j] равен нулю, то составляем список команд, с которыми эта команда ещё не играла(то есть этого элемента не было в столбце j) и которые ещё не играли в этом туре(строка i).
4. случайным образом выбираем из этого списка одну команду k и записываем число k ячейку [i, j] и соответственно j в ячейку [i, k]
вроде бы всё просто, однако порой вознивает ситуация, когда "не из чего выбирать", то есть те команды, с которыми текущая команда ещё не играла, уже участвуют в данном туре
И вот тут то я и застрял... мне кажется что должно быть какоето решение проще и "красивее" из комбинаторики или теории множеств, но, увы, я в этом не силён... может мне кто подскажет как это сделать?
|
Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 14 апр. 2008 18:34 | IP
|
|
Guest
Новичок
|
{7, 3, 2, 5, 4, 9, 1, 10, 6, 8, 13, 14, 11, 12},
{2, 1, 4, 3, 6, 5, 12, 11, 13, 14, 8, 7, 9, 10},
{3, 4, 1, 2, 7, 10, 5, 12, 11, 6, 9, 8, 14, 13},
{4, 5, 6, 1, 2, 3, 13, 14, 12, 11, 10, 9, 7, 8},
{5, 6, 7, 8, 1, 2, 3, 4, 14, 13, 12, 11, 10, 9},
{6, 7, 5, 9, 3, 1, 2, 13, 4, 12, 14, 10, 8, 11},
{8, 9, 10, 6, 11, 4, 14, 1, 2, 3, 5, 13, 12, 7},
{9, 8, 11, 12, 13, 14, 10, 2, 1, 7, 3, 4, 5, 6},
{10, 11, 8, 13, 14, 12, 9, 3, 7, 1, 2, 6, 4, 5},
{11, 10, 9, 14, 12, 13, 8, 7, 3, 2, 1, 5, 6, 4},
{12, 13, 14, 7, 8, 11, 4, 5, 10, 9, 6, 1, 2, 3},
{13, 14, 12, 10, 9, 8, 11, 6, 5, 4, 7, 3, 1, 2},
{14, 12, 13, 11, 10, 7, 6, 9, 8, 5, 4, 2, 3, 1}
Такая подойдет?
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 16 апр. 2008 17:46 | IP
|
|
krinart
Новичок
|
круть... я ожидал увидеть всё что угодно но только не готовую таблицу для 14 команд )) спасибо конечно тебе, Guest, но вобще я расчитывал на алгоритм, ну или хотябы идею, мне ведь нужно её случайным образом заполнять...
мне вот только интересно только как ты её получил?...
|
Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 16 апр. 2008 21:02 | IP
|
|
Guest
Новичок
|
{9, 3, 2, 5, 4, 7, 6, 14, 1, 13, 12, 11, 10, 8, 17, 18, 15, 16},
{2, 1, 4, 3, 6, 5, 8, 7, 14, 15, 13, 16, 11, 9, 10, 12, 18, 17},
{3, 4, 1, 2, 7, 8, 5, 6, 16, 14, 15, 17, 18, 10, 11, 9, 12, 13},
{4, 5, 6, 1, 2, 3, 9, 17, 7, 16, 18, 14, 15, 12, 13, 10, 8, 11},
{5, 6, 7, 8, 1, 2, 3, 4, 17, 18, 14, 13, 12, 11, 16, 15, 9, 10},
{6, 7, 5, 9, 3, 1, 2, 18, 4, 17, 16, 15, 14, 13, 12, 11, 10, 8},
{7, 8, 9, 6, 10, 4, 1, 2, 3, 5, 17, 18, 16, 15, 14, 13, 11, 12},
{8, 9, 10, 7, 11, 12, 4, 1, 2, 3, 5, 6, 17, 16, 18, 14, 13, 15},
{10, 11, 8, 12, 9, 13, 15, 3, 5, 1, 2, 4, 6, 18, 7, 17, 16, 14},
{11, 10, 12, 13, 8, 15, 16, 5, 18, 2, 1, 3, 4, 17, 6, 7, 14, 9},
{12, 13, 11, 10, 14, 17, 18, 16, 15, 4, 3, 1, 2, 5, 9, 8, 6, 7},
{13, 12, 14, 11, 16, 18, 17, 15, 10, 9, 4, 2, 1, 3, 8, 5, 7, 6},
{14, 15, 13, 17, 18, 16, 10, 11, 12, 7, 8, 9, 3, 1, 2, 6, 4, 5},
{15, 14, 16, 18, 17, 9, 11, 13, 6, 12, 7, 10, 8, 2, 1, 3, 5, 4},
{16, 17, 18, 14, 15, 10, 13, 12, 11, 6, 9, 8, 7, 4, 5, 1, 2, 3},
{17, 18, 15, 16, 12, 11, 14, 10, 13, 8, 6, 5, 9, 7, 3, 4, 1, 2},
{18, 16, 17, 15, 13, 14, 12, 9, 8, 11, 10, 7, 5, 6, 4, 2, 3, 1}
Вот для 18-ти. Что значит случайная - тут компонент связанности ~2n(n-1)/3. А перестановка строк? Например, таблиц 5x6 всего 5*144. Можно случайно выбирать из них.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 16 апр. 2008 21:23 | IP
|
|
krinart
Новичок
|
хорошо, допустим я могу переставлять строки и получать "случайную" таблицу... но как мне получать исходную неслучайную?.. я же не могу вручную вбить в алгоритм все варианты, начиная от 4-ёх команд и заканчивая к примеру 30-ю, а потом в зависимости от условия использовать только ту которая мне нужна...
|
Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 16 апр. 2008 22:03 | IP
|
|
Guest
Новичок
|
{8, 4, 7, 2, 6, 5, 3, 1},
{2, 1, 8, 5, 4, 7, 6, 3},
{3, 5, 1, 6, 2, 4, 8, 7},
{4, 8, 6, 1, 7, 3, 5, 2},
{5, 3, 2, 7, 1, 8, 4, 6},
{6, 7, 5, 8, 3, 1, 2, 4},
{7, 6, 4, 3, 8, 2, 1, 5}
-----------------------------
{3, 5, 1, 7, 2, 8, 4, 6},
{2, 1, 6, 8, 7, 3, 5, 4},
{4, 6, 7, 1, 8, 2, 3, 5},
{5, 3, 2, 6, 1, 4, 8, 7},
{6, 7, 8, 5, 4, 1, 2, 3},
{7, 8, 4, 3, 6, 5, 1, 2},
{8, 4, 5, 2, 3, 7, 6, 1}
Давайте рассмотрим две таблицы 7x8. Сколько в каждой из них случайных компонент, а сколько связанных? Каждая порождает 7! таблиц. Так, что здесь нужно уточнение. Как генерируются не случайные, вопрос решаемый, но, например, таблиц 7x8 больше 7*26000.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 16 апр. 2008 22:45 | IP
|
|
krinart
Новичок
|
прошу прощения за временное молчание...
я к сожалению не силён в научных терминах, я не знаю что такое случайные компоненты и связные, да мне в общемто и не важно их число... мне ведь нужна не математическая модель, а чёткий алгоритм...
я был бы очень признателен, если бы ты мне привел пример алгоритма генерации этих неслучаных таблиц, хотя бы в крупных командах, как я в самом первом посте написал свой алгоритм
|
Всего сообщений: 4 | Присоединился: апрель 2008 | Отправлено: 21 апр. 2008 21:37 | IP
|
|
|
Форум
Генерация таблицы игр чемпионата
