Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
udzhin
Member

Откуда:
Сообщений: 21
Доброго всем дня!
Бьюсь уже второй день над тем, как перевести алгоритм с бумаги в sql-код.

Имеется:
таблица results, хранит количество *голов* для команды набранных в игре конкретной недели
team_id int
team_score int

таблица standings, в которой записаны команды, их текущие очки, а также коэффициент Бухгольца (кол-во очков, которые набрали команды соперников для данной team_id за всю длину турнира)
team_id int
points int
buchholz int
сортируется по принципу order_by points desc, buchholz desc

таблица scheduleN, в которой есть столбцы team_id1 int, team_id2 int

таблицу scheduleN нужно заполнять между играми на основе истории по следующему алгоритму:
1) внутри групп очков ставим в team_id1 верхнюю половину группы, в team_id2 нижнюю половину.
2) если число команд внутри группы нечетное, то уменьшаем ее на 1, команду которую отцепили (это будет min(standings.buchholz) из очковой группы) - пишем в лидеры следующей очковой группы.
3) продолжаем итерации, пока не пройдем все team_id.

Не до конца понимаю, как можно реализовать момент для нечетного количества внутри группы.
Может кто-то помочь?
Ежели сумбурно и непонятно обьяснил - пишите, постараюсь подробнее.

Количество уникальных team_id - четное.
13 мар 17, 16:24    [20290329]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
Кесарь
Member

Откуда:
Сообщений: 463
udzhin
2) если число команд внутри группы нечетное, то уменьшаем ее на 1, команду которую отцепили (это будет min(standings.buchholz) из очковой группы) - пишем в лидеры следующей очковой группы.
3) продолжаем итерации, пока не пройдем все team_id.

Не до конца понимаю, как можно реализовать момент для нечетного количества внутри группы.


Вы ж сами только что написали, каков алгоритм. В чём вопрос-то?
13 мар 17, 17:00    [20290543]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
udzhin
Member

Откуда:
Сообщений: 21
Кесарь
udzhin
2) если число команд внутри группы нечетное, то уменьшаем ее на 1, команду которую отцепили (это будет min(standings.buchholz) из очковой группы) - пишем в лидеры следующей очковой группы.
3) продолжаем итерации, пока не пройдем все team_id.

Не до конца понимаю, как можно реализовать момент для нечетного количества внутри группы.


Вы ж сами только что написали, каков алгоритм. В чём вопрос-то?


Я его в код не могу завернуть. Вполне вероятно - просто не хватает компетенции в sql.
Внутри групп разбивал при помощи ntile 2, но тогда у меня не получается грамотно переписывать последнюю команду (заполнение столбца сползает).

Думаю, может попробовать ввести атрибут номера очковой группы после проверки на четность-нечетность, и уже на его основе луп для cur_points >-1, с понижением на единицу при каждом входе в цикл.

Не понимаю, как на sql ввести разбивку массива команд на очковые группы с четным числом участников в каждой из согласно алгоритму.
13 мар 17, 17:09    [20290584]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 942
udzhin,
На ваш сумбур напрашивается совет - выбросьте ту дурь, которую вы курите, и напишите нам изначальное ТЗ.

P.S. Потрудитесь предоставить хотя бы исходные данные, иначе помочь вам можно "общими" советами наподобие вышеизложенного.
13 мар 17, 17:57    [20290785]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
Кесарь
Member

Откуда:
Сообщений: 463
Вам легче всего будет реализовать цикл курсором. Собираете ваши команды в селект, отсортировав нужным образом. А потому тупо и в лоб делаете обход получившегося списка с заполнением нужных технических полей (для внутригрупповых отношений делаете просто напросто переменную-счётчик, которую и проверяете на чётность при каждом такте, как только пошло переполнение группы, то меняете принадлежность команды, а чтобы не запутаться в ID и порядке прохода, меняете не в теле курсора, а добавлением в отдельную техническую таблицу или поле new_goup_id).
13 мар 17, 18:01    [20290812]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 942
Кесарь
Вам легче всего будет реализовать цикл курсором.

Кыш-кыш!

udzhin, и что делать с командой, которая в итоге окажется в последней группе нечетной? будете кричать "ДНО!" и выпускать кракена?
13 мар 17, 18:21    [20290925]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
udzhin
Member

Откуда:
Сообщений: 21
Руслан Дамирович
Кесарь
Вам легче всего будет реализовать цикл курсором.

Кыш-кыш!

udzhin, и что делать с командой, которая в итоге окажется в последней группе нечетной? будете кричать "ДНО!" и выпускать кракена?


Лишней она не может оказаться по той простой причине, что count(team_id)mod2 = 0

Пример - 5 команд (1-2-3-4-5) с 1 очком, 3 команды (а-б-в) с 0
заполняем для 5:
1 3
2 4
5

добираем тремя
1 3
2 4
5 б
а в
13 мар 17, 18:49    [20291011]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 942
udzhin,
IF OBJECT_ID( N'tempdb..#teams_stats' ) IS NOT NULL
  DROP TABLE #teams_stats
;
CREATE
TABLE
  #teams_stats (
    [team] VARCHAR(50),
    [points] INT )
;
INSERT
INTO 
  #teams_stats
VALUES 
  ( 'Team1', 1 ),
  ( 'Team2', 1 ),
  ( 'Team3', 1 ),
  ( 'Team4', 1 ),
  ( 'Team5', 1 ),
  ( 'Team6', 0 ),
  ( 'Team7', 0 ),
  ( 'Team8', 0 )
;
DECLARE @team_count INT = ( SELECT COUNT(*) FROM #teams_stats )
;
IF @team_count % 2 != 0
BEGIN
  PRINT 'Выпускайте Кракена!'
  RAISERROR( 'ДНО!', 16, 1 )
END
;
IF OBJECT_ID( N'tempdb..#teams_stats0' ) IS NOT NULL
  DROP TABLE #teams_stats0
;
SELECT
  *,
  [gr] = DENSE_RANK() OVER ( ORDER BY [points] DESC )
INTO
  #teams_stats0
FROM
  #teams_stats
;
DECLARE @min_gr INT
SELECT @min_gr = ( SELECT TOP 1 [gr] FROM #teams_stats0 GROUP BY [gr] HAVING COUNT(*) % 2 != 0 )
WHILE @min_gr IS NOT NULL
BEGIN
  WITH
  ct AS (
    SELECT
      *,
      [rnm] = MAX( [rn] ) OVER ( PARTITION BY [points] )
    FROM (
      SELECT
        *,
        [rn] = ROW_NUMBER() OVER ( PARTITION BY [points] ORDER BY [team] )
      FROM
        #teams_stats0
      WHERE
        [gr] = @min_gr
      ) t
  )
  UPDATE
    ct
  SET
    ct.[gr] = ct.[gr] + 1
  FROM
    ct
  WHERE
        ct.[rnm] % 2 != 0
    AND ct.[rn] = ct.[rnm]
  ;
  SELECT @min_gr = ( SELECT TOP 1 [gr] FROM #teams_stats0 GROUP BY [gr] HAVING COUNT(*) % 2 != 0 )
  ;
END
;
WITH
gr AS (
  SELECT
    [gr],
    [pos] = SUM(1) / 2
  FROM
    #teams_stats0
  GROUP BY
    [gr]
  UNION ALL
  SELECT
    [gr],
    [pos] = [pos] - 1
  FROM
    gr
  WHERE
    [pos] > 1
),
ct AS (
  SELECT 
    *,
    [rn1] = ROW_NUMBER() OVER ( PARTITION BY [gr] ORDER BY [team] ),
    [rn2] = ROW_NUMBER() OVER ( PARTITION BY [gr] ORDER BY [team] ) - SUM(1) OVER ( PARTITION BY [gr] ) / 2
  FROM
    #teams_stats0
)
SELECT
  gr.[gr],
  gr.[pos],
  [team1] = t1.[team],
  [team2] = t2.[team]
FROM 
  gr
  INNER JOIN ct t1 ON (
        t1.[gr] = gr.[gr]
    AND t1.[rn1] = gr.[pos] )
  INNER JOIN ct t2 ON (
        t2.[gr] = gr.[gr]
    AND t2.[rn2] = gr.[pos] )
14 мар 17, 11:16    [20292528]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 942
Заменить
ROW_NUMBER() OVER ( PARTITION BY [gr] ORDER BY [team] )

на
ROW_NUMBER() OVER ( PARTITION BY [gr] ORDER BY [points] DESC, [team] )
14 мар 17, 11:30    [20292608]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм генерации расписания турнира на основе швейцарской системы  [new]
udzhin
Member

Откуда:
Сообщений: 21
Руслан Дамирович,

дякую!
14 мар 17, 11:33    [20292625]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить