Olösligt problem?

Är det udda antal så måste ett lag stå över varje omgång (eller något annat lag spela två matcher i en omgång, men det är bättre om alla står över en gång var)

Villkorsteknik (constraint programming) kan användas till sådant här. Ditt problem är en enkel variant av the sport scheduling problem, ett skolboksexempel och verkligt problem.
http://www.bit.spt.fi/cimmo.nurmi/ssp.htm (som du ser finns det många fler villkor man vill ta hänsyn till i en riktig schemaläggning i en liga).
edit: Eller vänta lite? Jag som snurrar till det. Ivf det exemplet vi hade i kursen var det en liga där det var jämnt antal lag, men 1 mindre omgångar än lag. Ditt är ju lite annorlunda i.o.m. att man har ojämnt antal och så många omgångar man behöver.

Jag håller på och filar på en lösning via villkorsprogrammering. Använder Gecode/J biblioteket. Men det krånglar lite, kommer med lösning sen.

Har hittat en girig lösning som fungerar i de fallen antal lag kan skrivas på formen 2^x-1. Detta är inte så värst användbart, men idéen är enkel.

Det är klart att för udda antal lag L så är antal matcher L*(L-1)/2. Vi kan därför alltid skapa L omgångar som vardera har (L-1)/2 matcher.

Vi tar exemplet att L=7. Det innebär att vi har 7 omgångar totalt med 3 matcher vardera. Vi skriver nu upp omgångarna och dessutom alla möjliga matcher i ordning.

1 2 3 4 5 6 x
1 2 3 4 5 x 7
1 2 3 4 x 6 7
1 2 3 x 5 6 7
1 2 x 4 5 6 7
1 x 3 4 5 6 7
x 2 3 4 5 6 7

1-2 1-3 1-4 1-5 1-6 1-7 2-3 2-4 2-5 2-6 2-7 3-4 3-5 3-6 3-7 4-5 4-6 4-7 5-6 5-7 6-7

Vi ska nu hitta permutationer av varje rad så att inga matcher sker två gånger. Första raden är enkel:

1-2 3-4 5-6

Vi är nu klar med 3 av 21 matcher och kan stryka de från listan:

1-2 3-4 5-6

1 2 3 4 5 x 7
1 2 3 4 x 6 7
1 2 3 x 5 6 7
1 2 x 4 5 6 7
1 x 3 4 5 6 7
x 2 3 4 5 6 7

1-3 1-4 1-5 1-6 1-7 2-3 2-4 2-5 2-6 2-7 3-5 3-6 3-7 4-5 4-6 4-7 5-7 6-7

I den andra omgången kan vi inte skapa en match av 1-2 eftersom vi redan använt den. Så vi tar den nästa matchen i lexiografisk ordning vilket är 1-3. Från
1 2 3 4 5 x 7
får vi
1-3 2-4 5-7

Fortsätter vi hittar vi en fungerande lösning

12 34 56
13 24 57
14 23 67
15 26 37
16 25 47
17 35 46
27 36 45

Detta fungerar dock bara som sagt för L=7, 15, 31 etc. För andra L (5 är ett bra exempel) går det inte att girigt plocka första bästa möjliga lösning från listan med möjliga matcher, då blir det en krock.

Edit: Jag gör en massa påståenden här som kanske berättigar nån slags bevis. Det är jag alldeles för lat för hehe.

Constraint programming handlar mycket om att modelera ett problem. Inte att skapa en algoritm för att lösa just ett specifikt problem. Vi ska ju ha datorn till för något, alltså beskriver vi villkoren i en modell och låter datorn räknat ut lösningar.

Här gör jag en enkel modell, jag gör inga anspråk på att den ska vara vidare effektiv, t.ex. har jag inga symmetribrytande villkor.

Kort sagt är det byggt som en matris där kolumnerna är spelarna. Problemet blir mycket enklare om man har en spökspelare, vi får då jämt antal spelare och det blir enkelt.
Vidare så är det en rad per omgång.
Värdet i varje cell säger vilken motspelare den spelaren ska ha. Det blir alltså dubbel information, då det på samma rad visas motspelaren möter den spelaren. Sen gjorde jag en utskrift i just det formatet (slö) så det är inte lika enkelt som 1-2, 3-4, 5-6... etc utskrift. När någon spelar mot spökspelaren skrivs det inte ut och det implicerar att spelaren ska stå över omgången.

För att kompilera och köra behöver man gecode/j biblioteket, men här är koden och utskriften. Eftersom du själv löst så gjorde jag allt statiskt för fem spelare, men det är inte det viktiga att här.

Edit: Jag kanske borde säga något generellt om hur villkorsprogrammering går till. Man sätter upp datan i modellen, postar villkor och ställer in branchning, när villkoren inte kan komma fram till en lösning så får man bygga ett sökträd där man tar någon variabel och fixerar den för att se om det kan bli en lösning då.

Liten guide till koden:
IntVar är en typ för decision variable (jag ville inte översätta det...).
Den har ett omfång med möjliga värden den kan komma att anta i en lösning, här ställs alla in till intervallet 0 - 5 (players).
distinct är ett villkor (även kallat allDifferent), alla värden i en array (av decision variables, inte programvariabler) måste anta olika värden.
rel är en simpel relation. Distinct skulle kunna beskrivas men jäkla massa rel:s.
channel_int beskriver x_i = j <=> y_j = i, här tar jag arrayen med sig själv för att beskriva att spelare x spelar mot y men att y också ska spela mot x, vilket annars inte påtvingas av modellen.

import static org.gecode.Gecode.*;
import static org.gecode.GecodeEnumConstants.*;
import org.gecode.*;

public class TSP extends Space
{
	VarMatrix<IntVar> schedule;
	private static final int players = 5;
	
	public TSP()
	{
		super("Tournament scheduling for odd number of players");
		
		/* Creates a matrix whith the width is player + 1 more and the height is player - 1.
		   First is because we use a dummy player, a ghost that when someone has to meet it they don't play.
		   Second is because we will never play against ourself.
		*/
		schedule = new VarMatrix<IntVar>(this, players - 1, players + 1, IntVar.class, 0, players);
		
		for (int i = 0; i < players + 1; i++)
		{
			VarArray<IntVar> col = schedule.col(i);
			
			distinct(this, col); // only meet the same player at most once
			
			for (int j = 0; j < players - 1; j++)
				rel(this, col.get(j), IRT_NQ, i); // prevent against meeting him/her self
		}
		
		for (int j = 0; j < players - 1; j++)
		{
			VarArray<IntVar> row = schedule.row(j);
			
			distinct(this, row); // Play only once per period
			
			/* Make sure that matching goes both ways, i.e. if player 2 plays against player 4,
			   then player 4 should also play against player 2. */
			channel_int(this, row, row);
		}
		
		// This flattens out the matrix, thus branching can be done
		VarArray<IntVar> BA = new VarArray<IntVar>(schedule);
				
		// Branch, go with the variable which have the smallest domain and test the smallest value
		branch(this, BA, INT_VAR_SIZE_MIN, INT_VAL_MIN);
	}
	
	public TSP(Boolean share, TSP tsp)
	{
		super(share, tsp);
		schedule = new VarMatrix<IntVar>(this, share, tsp.schedule);
	}
	
	public String toString()
	{
		String result = new String("The tournament schedule:\n");
		
		result += "Player: 1 2 3 4 5\n";
		for (int i = 0; i < players - 1; i++)
		{
			VarArray<IntVar> row = schedule.row(i);
			result += "\n" + (i + 1) + "#     ";
			
			for (int j = 0; j < players; j++)
			{
				if (row.get(j).assigned())
				{
					if (row.get(j).val() != 5) // 
						result += " " + (row.get(j).val() + 1);
					else
						result += "  ";
				}
				else
				{
					// Will never happen if we have a solution
					result += " [[[NOT ASSINGED min: " + row.get(j).min() + " max: " + row.get(j).max() + " ]]]";
				}
			}
		}
		
		
		
		return result;
	}
	
	public static void main(String[] args)
	{		
		TSP tsp = new TSP();
		
		DFSIterator<TSP> iter = new DFSIterator<TSP>(tsp);
		
		if (iter.hasNext())
			System.out.print(iter.next());
		else
			System.out.println("No solutions!??");
		
		// Instead if you want all the solutions
		/*
		while (iter.hasNext())
		{
			System.out.println(iter.next());
		}
		*/
	}
}

Utskrift.
Ex. Spelare 2 möter spelare 1 i första omgången. Spelare 5 spelar inte i 1 men möter spelare 2 i andra omgången.

Player: 1 2 3 4 5

1#      2 1 4 3
2#      3 5 1   2
3#      4   5 1 3
4#      5 4   2 1

i C sent på natten kodning, djupet först rekursiv:
fungerar inte för 9 av någon anledning men orkar inte felsöka nu

Edit: någon alvarlig bugg göra att det fungerar dåligt över 8

#include <stdio.h>
#include <stdlib.h>
int teams;
int matches=0;
volatile int oldi[100];
volatile int oldj[100];
int array[100][100];
int max=0;
int first =1; 
int find (int i, int j){
   int ii=0, jj=0,k=0,doit=0;
   oldi[(((teams+1)/2)-1+matches)%((teams+1)/2)]=i;
   oldj[(((teams+1)/2)-1+matches)%((teams+1)/2)]=j;
   for(ii=0;ii<teams;ii++){
      for(jj=0;jj<teams;jj++){
         doit=1;
         for(k=0;k<(matches)%((teams+1)/2);k++){
            if(((oldi[k]==ii || teams-oldj[k]==ii || teams-oldi[k]==jj || oldj[k]==jj) && (matches%((teams+1)/2)!=0))){
               doit=0;
            }
         }
         if (first) {
            doit=1;
            first=0;
         }
         if(doit==1){
            if(doit!=1)exit(0);
            if( array[ii][jj]!=0){
               array[ii][jj]=0;
               matches ++;
               if(find(ii,jj)){
                  printf("%u - %u ",ii+1,teams-jj+1,matches);
                  matches--;
                  if(matches%((teams+1)/2)==0)
                     printf("\n");
                  return 1;
               }
               if (matches ==max){
                  printf("%u - %u ",ii+1,teams-jj+1,matches);
                  matches--;
                  return 1; 
               }
               oldi[((teams+1)/2)-1+matches%((teams+1)/2)]=i;
               oldj[((teams+1)/2)-1+matches%((teams+1)/2)]=j;
               matches --;
               array[ii][jj]=1;
            }}
      }
   }
   return 0;   
}
int main (int argc, char ** argv[]){
   int i,j;
   teams = atoi(argv[1]);
   teams--;

   for (i=0; i<10; i++){
      for (j=0;j<10; j++){
         array[i][j]=0;
      }
   }
   for (i=0; i<teams; i++){
      for (j=teams;j>i; j--){
         array[i][teams-j]=1;
         max++;
      }
   }
   if(find(0,0)) printf("success\n");
}

Ett intressant problem som det har ägnats en del tid åt att lösa effektivt.
Sökrummet är någonstans i närheten av (n/2 * (n-1))! olika permutationer, så för fall upp till n=16 så ska dagens datorer lösa problemet under 10 sekunder.

kika på dessa papper:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.74...
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.9...

Jag kan testa att knåpa ihop ett senare. Men är det exakt samma sak du vill göra som trådskaparen? Egentligen kan man ju bara mata in ett antal ojämna tal och du kan få svaren, det är ju bara att lotta om vem som ska representera vilken siffra så har man ju lite olika matchtyper.

Jag testade lite, mitt icke-tweakade program tog för 101 spelare ca. 13 cpu-sekunder, jag har quad core och processen använde ~50% (dvs två kärnor och det då är 13 sekunder i verkligheten 6,5 sekunder). Kom upp i 3 GiB minnesanvändning också (men tur att man har mycket att undanvara, inget swappande här inte )

Så med de här få villkoren vi har så har vi redan datorkraft nog att lösa alla problem, ty med 101 spelare och det här uppläget på matcher så får man spela 101 ! = 9.42594776 × 10^159 matcher, inte vidare praktiskt

Skulle bara vilja bidra med en alternativ lösning.

Bygg en graf där man har en nod för varje match som ska spelas och en båge mellan varje match som inte kan spelas i samma omgång.

Sen kan man se problemet som att färga denna graf, läs mer här.
http://en.wikipedia.org/wiki/Graph_coloring

Varje färg blir alltså en omgång och noderna med den färgen blir matcherna som ska spelas i den omgången.

Det ska dock tilläggas att problemet att färga en graf är NPC (iallafall någon variant på det). Det är möjligt att man kan hitta en bättre algoritm genom att utnyttja den speciella strukturen i denna grafen...

EDIT: Ok jag insåg nu att detta enklare modelleras med att "båg färga" en komplett graf. Detta finns det mycket snabba algoritmer för. Läs "theorem 3" i

http://www.kurims.kyoto-u.ac.jp/~iwata/dmi/dmi02e.pdf

för hur det går till.

Jag implementerade detta i python. Jag skulle tro att detta är mycket snabbare än alla andra lösningar som givits i denna tråd. Till exempel löser den fallet på 1000 spelare på under 1 sek.

def solve(n):
    even = (n%2 == 0)
    if even:
        n-=1
    
    match = []
    for i in range(n):
        match.append([])

    for i in range(n):
        for j in range(i+1, n):
            match[(i+j)%n].append((i,j))

    if even:
        for i in range(n):
            match[(2*i)%n].append((i,n))
    return match

def print_solution(match):
    k = 1
    for o in match:
        print "Omgang " + str(k)
        k+=1
        for m in o:
            print str(m[0])+"-"+str(m[1])
        print ""

players = 5
print_solution(solve(players))

Damn det där var inte dåligt snyggt jop! En sann lösning att vara lite avundsjuk att man inte tänkte ut själv.

Har du jobbat mycket med grafalgoritmer tidigare eller "kom" lösningen bara?

Oh tack

Jag går teknisk matematik i Lund så det är väll sånt här som jag ska kunna

lattjo, jag går också teknisk matematik (håller på med exjobb nu)
jop_the_jopsan, vilket år läser du och vilken inriktning?

Läser 2:an nu. Ingen inriktning än då alltså. Kul med fler pi:are på swec

Kan inte vb men det det kanske är lättare att läsa som c++? Dessutom liten variant på upplägget som använder konstant minne (om man inte räknar utskriften då).

#include <iostream>

using namespace std;

int main(int argc, char** argv) {
	int players;
	cin >> players;

	bool even = (players%2==0);
	if(even)
		players--;

	for(int n=0;n<players;n++) {
		cout << "Omgang " << n << endl;
		for(int p1=0;p1<players;p1++) {
			int p2=(n-p1+players)%players;
			if(p1 < p2)
				cout << p1 << "-" << p2 << endl;
			if(p1 == p2 && even)
				cout << players << "-" << p1 << endl;
		}
	}
	return 0;
}

Python är ju nästan ren engelska