스포츠 리그 일정을 자동으로 생성하는 방법

StackOverflow https://stackoverflow.com/questions/1037057

  •  10-07-2019
  •  | 
  •  

문제

나는이 주제가 복잡하고 아마도 쉬운 대답이 없다는 것을 이해한다고 말함으로써 시작하겠습니다. 쉬웠다면 모두가 그렇게 할 것입니다. 그 말 ...

스포츠 리그를 관리하기위한 응용 프로그램을 구축하라는 요청을 받았습니다. 대부분의 개념은 이것을 제외하고는 이해하기 쉽습니다. 겹치지 않는 곳에서 플레이 일정을 생성하는 방법 (한 번에 2 팀을 플레이 함). 다른 부서는 한 번, 일정에 구멍이 없는지 확인합니다 (각 팀은 매주 재생됩니다)

현재이 프로세스는이 목적을 달성하기 위해 제작 한 Rosetta Stone 유형 스프레드 시트를 사용하여 수동으로 수행되지만 설계된 팀 수에만 적용됩니다. 30 팀, 24 개 팀 및 28 개 팀에 대한 변형이 있습니다. 번역 테이블을 지속적으로 재조정하려고 시도하는 대신 해당 논리를 체계화하고 대신 그 프로세스를 조정할 수 있기를 원합니다.

생각?

도움이 되었습니까?

해결책

Round-Robin이라는 예를 들어 체스 토너먼트에 사용되는 매우 간단한 시스템이 있습니다.

아이디어는 플레이어를 테이블의 양면으로 나누는 것입니다. 플레이어 중 하나는 "허브"로 지정됩니다 (더 나은 단어를 원하기 위해). 토너먼트는 플레이어가 서로 마주 치게함으로써 시작됩니다. 첫 번째 라운드 후에는 모두를 제외한 모든 사람 이외의 허브가 하나의 의자를 앞으로 움직이고 흰색/검은 색 (홈/스포츠) 주문이 전환됩니다. 전체 라운드 로빈 대회는 플레이어가 원래 장소에 앉을 때 완료됩니다. 모든 사람이 모두를 두 번 플레이하기를 원한다면 다시 똑같이합니다.

위키 백과 기사 구현 세부 사항이 있습니다.

당신의 특별한 경우에 나는 모든 팀을 포함하여 라운드 로빈을 한 번 시도 할 것입니다. 그런 다음 각 부문에 대해 한 번도 동일하게 수행하고 부서 내 팀이 집에서 한 번 서로 연주하고 한 번은 팀이 그 라운드에서 어떤 방식으로 플레이했는지 확인하십시오.

물론이 중 하나는 토너먼트 마감 전에 모든 차별적 경기를 잘 수행한다는 것입니다 (마지막 N-1 경기는 다발 내 팀과의 경기 [N = 디비전의 팀 수])입니다. 이것이 문제라면 단순히 일치를 약간 바꿀 수 있습니다.

나는 실제로 이것을하는 간단한 파이썬 스크립트를 썼습니다. 그것은 많은 코드 라인을 사용하지 않았으며 꽤 좋은 결과를 얻었습니다. 이렇게하면 각 팀이 각 팀이 디비전에서 두 번, 다른 부서의 팀에 대해 한 번 플레이하는 일정을 만듭니다. 그러나 동일한 팀이 집에있는 방식으로 팀이 서로 두 번 만나는 지 확인할 수 없습니다. 그러나이 코드는 자신의 스케줄링 코드를 만드는 방법에 대한 좋은 아이디어를 제공해야합니다.

#!/usr/bin/python

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]

def create_schedule(list):
    """ Create a schedule for the teams in the list and return it"""
    s = []

    if len(list) % 2 == 1: list = list + ["BYE"]

    for i in range(len(list)-1):

        mid = int(len(list) / 2)
        l1 = list[:mid]
        l2 = list[mid:]
        l2.reverse()    

        # Switch sides after each round
        if(i % 2 == 1):
            s = s + [ zip(l1, l2) ]
        else:
            s = s + [ zip(l2, l1) ]

        list.insert(1, list.pop())

    return s


def main():
    for round in create_schedule(div1):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div2):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div3): 
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div1+div2+div3): 
        for match in round:
            print match[0] + " - " + match[1]
        print

if __name__ == "__main__":
    main()

다른 팁

두 가지 알고리즘이 있습니다. 하나는 홀수 팀을위한 하나, 하나는 라운드 로빈이 발생하는지 확인하기 위해 팀을위한 것입니다.

가능하다면 그래픽을 생성 할 것입니다.

팀의 홀수 #

알고리즘은 모든 팀을 시계 방향으로 회전시키는 것입니다. 5 개 팀이 있다면 :

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4     5 2     4 1     2 3     1 5
5       4       2       1       3

이 시점에서 우리는 모두가 서로 한 번 서로 연주하는 한 라운드 로빈을 완성했습니다 ... 다음 라운드는 다시 ..

1 2
3 4
5

팀의 #조차도

우리가 짝수의 팀이 있으면, 당신은 팀 #1을 고정 위치로 유지하고 시계 방향으로 #1 주위에 다른 모든 팀을 회전시키는 것을 제외하고는 동일한 로테이션을합니다. 그래서 우리가 4 개의 팀이 있다면 ..

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3

이것은 하나의 완전한 라운드 로빈 일 것입니다 ... 다음 경기는 ..

1 2 
3 4

프로그래밍 방식으로, 당신이 이것에 접근 할 수있는 몇 가지 방법이 있습니다. 위에 게시 된 코드는 똑같은 일을 할 것입니다 ..

나는 이러한 제약을 부울 공식으로 인코딩하고 일부 Sat-Solver를 사용하여 솔루션 (예 : C ++ 용 Minisat, Java의 경우 Sat4J, 간단한 솔버를 쓸 수도 있음)을 얻을 수 있습니다. 이 솔버에 대한 입력은 Dimacs에 의해 견딜 수 있습니다.

또한 "소셜 골퍼 문제에 대한 SAT 인코딩"및 "토너먼트 일정을위한 SAT 기반 스케줄러"를 참조하십시오.

구현시 촬영이 있습니다

public interface ITeam
{
   bool PlaysOn(DateTime date);
   bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice   
                        //already, same different divisions and other applicable rules
}

IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();

foreach(var date in gameDays)
{
   for(int i = 0;i<count;i++)
   {
      var innerTeams = i % 2 == 0 ? teams : reversed;
      var team = (from t in innerTeams
                  where !t.PlaysOn(date)
                  select t).First();  
      var opp = (from t in teams
                 where !t.PlaysOn(date) && t.CanPlay(team)
                 select t).First();
      SetupGame(team,opp);
   }
} //lot of optimazation possible :)

나는 종이에서만 테스트했지만 설정을 위해서는 작동합니다. 팀 목록의 시작 부분에서 시작하여 목록의 끝 사이를 번갈아 가면서 같은 팀이 동일한 팀을 반복해서 반복해서 (또는 같은 날에 반복적으로 플레이 해야하는) 상황을 피합니다. 가능한 모든 만남을 다른 opponnent로 표현했지만 기본적으로 Canplay 방법이해야 할 일입니다. 이것이 도움이되기를 바랍니다. 완전한 해결책이 아닙니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top