Problema matemático

Archivado
Lo primero, no se si este es el lugar indicado, espero que si, si no es asi movedme el post.

A ver mi problema:
Tengo que organizar a unos muchachos para una acampada y tengo que hacer unos juegos.
Los he organizado en en 20 equipos y tienen 10 estaciones de juego, queria hacer que en todo momento estuviesen todos compitiendo en alguna estación sin tener a nadie parado y la parte mas compleja, quiero que cada vez compitan con un equipo distinto... no se si me explico. llamemos a los juegos por letras A, B, C... y a los equipos los numeramos del 1-20.
En el juego a las 12.00h tenemos a los equipos 1vs10 en el juego A al 2vs12 en el B al 3vs13 en el C, la primera linea es facil, pero luego ir completandolas sin que se repitan como he dicho y evidentemente jugando cada vez a un juego distinto pues me resulta imposible.

Quería saber si alguien sabe alguna formula para aplicar para que me vayan saliendo, se que existe pero no doy con ella. (ejemplo NvsM; N+1vsM-1...) hasta ahora lo mejor que he conseguido es que al final del dia cada equipo juegue contra los otros equipos pero repitiendose con uno y faltando uno contra quien emparejarse.

Venga que salgán los que organizan los torneitos de futbol de su barrio y me lo consigan ordenar, que tengo un caos.. jajajaj

Gracias a todos.
Suena bastante interesante, me viene perfecto para practicar.

Si me das los detalles concretos, puedo hacerte un programa que te genere un horario aleatorio.
Pero eso es un problema más de satisfacción de restricciones, ¿no? Es decir, que no hay una fórmula matemática que te empareje a los equipos.

P.D.: siento si la pifio, pero estoy muerto :P.
(mensaje borrado)
Se me ocurre, por aquello de hacerlo fácil, que los emparejamientos los hagas como en una liga de 20 equipos. El procedimiento es muy sencillo. Si quieres una explicación de cómo hacerlo, aquí tienes una:

http://es.wikipedia.org/wiki/Sistema_de ... de_fixture

Luego, como además vas a tener distintos juegos, simplemente asigna a cada columna de la tabla un juego distinto, que será el que jueguen los equipos correspondientes. A tener en cuenta que si quieres enfrentamientos "todos contra todos", necesitas 19 rondas para 20 equipos, con lo que cada equipo jugará 2 veces a cada juego excepto a uno de ellos, que lo hará solo una vez.
Vale veo ideas, asique voy a desarrollarlo un poco más.

Cada juego dura 20 minutos asique vamos a tener estos horarios:
17.00-17.20
17.20-17.40
17.40-18.00
18.00-18.20
18.20-18.40
18.40-19.00
19.00-19.20
19.20-19.40
19.40-20.00
20.00-20.20

Como veis hay 10 horarios para que cada grupo juegue a un juego cada vez.
Por otro lado tenemos 10 juegos, los podemos clasificar por letras: A,B,C,D,E,F,G,H,I,J.
y cada equipo se pueden numerar del 1 al 20.
Entonces la tabla (sin los enfrentamientos sería asi)
.....................Juego A Juego B Juego C Juego D Juego E Juego F Juego G Juego H Juego I Juego J
17.00-17.20
17.20-17.40
17.40-18.00
18.00-18.20
18.20-18.40
18.40-19.00
19.00-19.20
19.20-19.40
19.40-20.00
20.00-20.20

El problema aqui respecto a la idea de hacerlo como la liga es que tenemos 3 factores:
El juego en el cual no puede jugar dos veces el mismo equipo, es decir que ningún equipo se repita en la misma columna
El horario, en el cual ningún equipo puede estar en dos juegos distintos a la misma hora, es decir, que ningún equipo se repita en una misma fila.
Y el factor [sati] de que ningún equipo repita contra otro.
Yo de momento he conseguido hacer una tabla con los dos primeros factores perfect pero cada equipo repite con uno y se queda sin jugar con otro.
Y evidentemente no puedo tener a ningún equipo sin jugar en ningún momento.
288, me sorprende que nadie le haya respondido todavía.
Codeando un miniprograma me ha generado la siguiente configuración:
Imagen

https://dl.dropboxusercontent.com/u/695 ... orario.txt

Revisala pero no debería tener errores.
Uff muchas gracias pero no me vale, no se si me he explicao mal.
La tabla que me has puesto esta perfect para organizar los juegos, pero no tiene en cuenta el factor horario, entonces no me vale porque por ejemplo en la primera fila el equipo 7 se repite varias veces, lo que significa que estarian en varios juegos a la misma vez y es ahi donde reside el problema que soy incapaz de resolver.
Gracias de todas formas
Solo tienes 10 intervalos horarios (10 jornadas para entendernos), por lo que es imposible que cualquier equipo se enfrente a los restantes diecinueve, o lo que viene a ser lo mismo, cada uno jugará solo diez partidas. No se puede hacer un "todos contra todos".
Deschamps escribió:Solo tienes 10 intervalos horarios (10 jornadas para entendernos), por lo que es imposible que cualquier equipo se enfrente a los restantes diecinueve, o lo que viene a ser lo mismo, cada uno jugará solo diez partidas. No se puede hacer un "todos contra todos".


ya eso lo entiendo, lo que quiero hacer es que se enfrenten los del 1 al 10 contra los del 11 al 20
pero que no se repitan ni se dejen ninguno sin jugar
Ops, fallo técnico. Solo me he preocupado de las columnas, se me olvidaban las filas jejje

Ahora tengo que irme, esta noche actualizare.

PD: Como bien Deschamp, cada equipo jugara con 10 equipos diferentes. Pero no contra todos.
FurbyDh escribió:ya eso lo entiendo, lo que quiero hacer es que se enfrenten los del 1 al 10 contra los del 11 al 20
pero que no se repitan ni se dejen ninguno sin jugar


Lo estás complicando en exceso. Calcula 10 permutaciones para 20 elementos, sin que repitan posición ninguno de ellos. Y emparejas dos a dos.
amchacon escribió:Ops, fallo técnico. Solo me he preocupado de las columnas, se me olvidaban las filas jejje

Ahora tengo que irme, esta noche actualizare.

PD: Como bien Deschamp, cada equipo jugara con 10 equipos diferentes. Pero no contra todos.


Gracias máquina.
Ya, lo de que no sea contra todos me es indiferente. quiero que cada uno se empareje a otros 10 y que cada vez sean distintos.

Deschamps escribió:
FurbyDh escribió:ya eso lo entiendo, lo que quiero hacer es que se enfrenten los del 1 al 10 contra los del 11 al 20
pero que no se repitan ni se dejen ninguno sin jugar


Lo estás complicando en exceso. Calcula 10 permutaciones para 20 elementos, sin que repitan posición ninguno de ellos. Y emparejas dos a dos.


Ummm tienes razón calculandolo como 20 elementos separados en vez de como lo estaba haciendo seguramente sea mas facil, pero no se hacer que no repitan posición...

PD: Mis matematicas quedaron en bachillerato ¬_¬ (asique no se hacer nada mas alla de lo que enseñan ahí, incluso algo se habrá olvidado...) ahora con el temario de bombero tengo suficiente [+risas] [+risas]
Si estableces los juegos en letras (A,B,C,D,E,F,G,H,I,J) y a cada juego le asignas 2 equipos (A --> equipo 1 vs equipo 2).
Simplemente haz que el primer equipo se desplace al siguiente juego (A-->B) y el segundo equipo que se desplace 2 juegos (A-->C). Con este sistema necesitarías los diez juegos para que se vuelvan a juntar los mismos equipos.

Un saludo.
Tristar escribió:Si estableces los juegos en letras (A,B,C,D,E,F,G,H,I,J) y a cada juego le asignas 2 equipos (A --> equipo 1 vs equipo 2).
Simplemente haz que el primer equipo se desplace al siguiente juego (A-->B) y el segundo equipo que se desplace 2 juegos (A-->C). Con este sistema necesitarías los diez juegos para que se vuelvan a juntar los mismos equipos.

Un saludo.


No, entonces el segundo equipo repetiría juegos en la 2ª ronda (jugaría a los mismos 5 dos veces, y dejaría 5 sin probar)
¿Y esto es para un solo día o para dos? Porque si fuera para dos, es casi inmediato (aunque con 21 equipos en lugar de 20, y descansando uno en cada ronda).
Para un solo dia y los equipos deben ser 20

Eso que has dicho de A-B 1-2 es de lo primero que probé pero se repiten en el horario
Problemas de este tipo los di en la carrera, pero no me acuerdo de nada. La asignatura era Investigación Operativa, las restricciones eran Programación Lineal y el modo de resolverlo era el Algoritmo Simplex (Que simple simple tampoco era).

http://es.wikipedia.org/wiki/Algoritmo_s%C3%ADmplex

Busca algún programa que te resuelva las ecuaciones, que los hay a montones.
SFII escribió:Problemas de este tipo los di en la carrera, pero no me acuerdo de nada. La asignatura era Investigación Operativa, las restricciones eran Programación Lineal y el modo de resolverlo era el Algoritmo Simplex (Que simple simple tampoco era).

http://es.wikipedia.org/wiki/Algoritmo_s%C3%ADmplex

Busca algún programa que te resuelva las ecuaciones, que los hay a montones.


UHHH [flipa] he leido que era y tal y despues de un rato de descubrir un idioma nuevo he buscado programas y cuando me pongo a ello me pone inserte las ecuaciones y ahi me ha dado Syntax error en la pantalla oled de mi cerebro y diria que acompañado de un mensaje que decia que mi probabilidad de ictus habia aumentado en un 3% [fumeta]

Todo eso es high level para mi...
Si quieres considerar unos cambios... Por ejemplo, si decides que el tiempo que pasa jugando cada equipo en lugar de ser 10 "rondas" de 20 minutos, fuese 20 "rondas" de 10 minutos, al final acaban jugando el mismo tiempo y (aunque parezca un cambio sin trascendencia) eso permite resolver el problema. Eso sí, cada equipo pasaría también 10 minutos de descanso, porque tendrías que crear un equipo adicional para que cuadre el tema.

Además, te aseguras que todos los equipos participan en todos los juegos (2 veces en cada uno) y que todos juegan también contra el resto de adversarios (que es lo lógico). Es un simple round-robin que además alterna visitante/local en cada ronda, si eso fuera necesario.
XD todos los programadores somos iguales, intentamos retorcer la realidad para que se adapte a lo que necesitamos.
21 respuestas
Archivado
Volver a Miscelánea