Algo difícil

[Rioja72]

Hola delphian@s, no sé por dónde empezar, a ver si me dáis alguna pistilla.

El problema es que tengo dos listas <A> y <B>, debo emparejar cada elemento de la lista <A> con cada uno de la lista <B>, pero haciendo grupos de <n> parejas, habrá que hacer tantos grupos como sea necesario para completar las <cantidad(A) * cantidad(B)> de parejas posibles.

Estoy pensando en el "vuelta atrás" pero no sé cómo implementar las listas.

Por ejemplo:
Dos listas de 4 elementos, y grupos de 3
G1 G2 G3 G4 G5 G5
A1-B1 A4-B4 A3-B1 A2-B1 A1-B4 A2-B4
A2-B2 A1-B2 A4-B2 A3-B4 A3-B2
A3-B3 A2-B3 A1-B3 A4-B3 A4-B1

además, como podéis ver, no hay elementos que se queden fuera de grupo en dos ciclos seguidos.

[ContraVeneno]

Bienvenido al foro, te recomiendo leer la guía de estilo. Esto es para que te podamos ayudar y nos ayudes un poquito.

Ahora referente a tu problema, no entendí nada... ¿dos listas? ¿de qué?, ¿dónde están guardadas o como están almacenadas? y un inumerable etc de preguntas. Si nos das un poco más de información, nos muestras que estas haciendo o algo más de detalles, seguro que alguien podrá ayudarte.

[[duilioisola]]

debo emparejar

¿Hay algún criterio para emparejar o cualquiera con cualquiera?

cada elemento de la lista <A> con cada uno de la lista <B>, pero haciendo grupos de <n> parejas

¿Cómo obtienes n?

habrá que hacer tantos grupos como sea necesario para completar las <cantidad(A) * cantidad(B)> de parejas posibles

Si cantidad(A) =5 y cantidad(B)=3 debes hacer 15 parejas.
Cómo obtienes la cantidad de grupos?
- 3 gupos de 5 parejas
- 5 grupos de 3 parejas
- 15 grupos de 1 pareja
- 2 grupos,uno de 7 y otro de 8 parejas

[Rioja72]

Hola, para emparejar no hay criterios, son todos los de la lista A con todos los de la lista B.
Pensemos en equipos de fútbol, vamos a hacer un campeaonato de la 1ª división contra la 2ª, cada equipo de 1ª debe jugar contra cada equipo de 2ª (lista A y lista B) pero sólo tenemos <n> campos (los que nos indique el usuario), de esta forma habrá equipos que tengan que descansar en cada jornada, pero que no descansen 2 jornadas seguidas. La cantidad de jornadas depende, por lo tanto, de la cantidad de equipos y de campos.
En tu ejemplo: 5 equipos de 1ª y 3 de 2ª implican 15 partidos, si el usuario dice que tenemos 2 campos (grupos) pues habrá 8 jornadas (7 completos y luego 1).

espero haberme explicado mejor.

[fidel]

Utilizo algo muy similar que hice hace algunos años para gesitonar torneos internos, lo que pasa que no recuerdo bien los detalles de como lo hice, pero más o menos es así.

Primero hay que generar los partidos y luego ya se reparten en jornadas y campos.

Generar los partidos.

Pon en una tabla auxiliar (o un array) los equipos de 1ª de nombre PRIMERA y en otra tabla (o array) los equipos de 2ª de nombre SEGUNDA, y crea otra tabla auxilar llamada PARTIDOS con dos campos LOCAL, VISITANTE
Recorre con un bucle la tabla PRIMERA y dentro otro bucle para recorrer la tabla SEGUNDA y así vas formando los partidos que vas añadiendo a la tabla PARTIDOS con el equipo de 1ª como local y el de 2ª como visitante. Una vez terminados los bucles tendrás todos los partidos que hay que jugar. Si es a ida y vuelta se añaden los mimos partidos pero invirtiendo el orden de los equipos.

Ahora repartir todos los partidos de la tabla PARTIDOS en las distintas jornadas y campos, esto es un poco trabajoso pero no es dificil, es más dificil de explicar que de hacer. A ver si lo logro.

Necesitaremos otra tabla que puedes llamar JORPARTI con estos campos: JORNADA, FECHA, CAMPO, PARTIDO
Hay que ir recorriendo la tabla PARTIDOS tantas veces como sea necesario (con un bucle While condicionado) hasta que quede vacía (si vamos borrando los partidos que añadimos) o hasta que queden todos marcados como asiganados (si lo hacemos teniendo un campo que ponga asignado). Esto es complicado, sobre todo para explicarlo. Lo intento.

Pongo en una variable "jornada" el valor 1, cojo la fecha de la primera jornada en una variable "fecha" (lo tendrás en algún sitio) y el nº de campos para la primera jornada en otra variable "ncampos" (también lo tendrás en algún sitio), añado un registro en JORPARTI y relleno JORNADA con el valor de "jornada" ), CAMPO con el valor de "ncampos" , FECHA con la "fecha" y PARTIDO con el primer partido de la tabla PARTIDOS que estamos recorriendo, ahora hay que restar 1 al valor de "ncampos" con la condición que si se queda a 0 hay que volver a ponerle el valor máximo de campos existentes, y borrar el registro del partido que hemos añadido.
Después habrá que ir añadiendo en la misma jornada los demás partidos pero contralando que en ellos no haya un equipo que ya esté jugando.

Mejor te pongo un ejemplo porque me estoy liando.

Tabla PRIMERA con 3 registros (3 equipos): Racin, Real, Unión.
Tabla SEGUNDA con 3 registros (3 equipos): Uno, Dos, Tres.
Un bucle recorriendo la tabla PRIMERA y otro dentro recorriendo la tabla SEGUNDA nos da las parejas que vamos añadiendo a la tabla PARTIDOS
Racin Uno
Racin Dos
Racin Tres
Real Uno
Real Dos
Real Tres
Unión Uno
Unión Dos
Unión Tres

Con solo 2 campos para jugar

variables:
jornada:=1
fecha:=15-11-2010
ncampos:=2
partido:=Racin Uno (valor del primer registro)

Añado un registro en JORPARTI y relleno campos con el valor de las variables
JORNADA con variable jornada
FECHA con variable fecha
CAMPO con variable campo
PARTIDO con variable partido

Resto uno al valor de campo pongo un if que si se queda a 0 hay que asignarle el valor 2 (nº de campos que tengo) y sumar uno a jornada (jornada siguiente) y cambiar fecha con la fecha de la siguiente jornada
Borro el primer registro de partidos

Ahora un bucle sin fin hasta que se quede vacia la tabla partidos
Pongo en la variable partido el partido actual (sería Racin Dos)
Aquí hay que comprobar en la tabla JORPART que en esta misma jornada no esté ya alguno de estos dos equipos en otro partido, esto no es dificil de coprobar, en este caso veríamos que el Racin ya está por lo tanto deberíamos avanzar un registro en PARTIDOS coger el nuevo partido y hacer la misma comprobación hasta que ninguno de los dos equipos de este partido esté ya asignado a esa jornada y podamos añadir el partido en esa jornada, en cuyo caso ...

... resto uno al valor de campo pongo un if que si se queda a 0 hay que asignarle el valor 2 (nº de campos que tengo) y sumar uno a jornada (jornada siguiente) y cambiar fecha con la fecha de la siguiente jornada
y borro el registro de partidos (ahora no hace falta avanzar porque al borrar ya me he colocado en el siguiente partido)

Bueno, creo que me he explicado bastante mal, porque no es simple, y tendría que simplificar la explicación, pero espero que te sirva para darte una idea de como se puede hacer, aunque supongo que habrá otra formas y probablemente más fáciles.

A mano te prodría dibujar algo que se entendería mejor.

Un saludo.

[Rioja72]

Muchísimas gracias Fidel, me lo había planteado algo así, pero es que no pueden descansar dos jornadas seguidas, entonces habría que echar marcha atrás (al menos al hacerlo manual me ha ocurrido), por esto estoy pensando en el "vuelta a atrás".

Un saludo.

[[duilioisola]]

Se me ocurre que hagas una matriz de cantidad(A) x cantidad(B). En mi anterior ejemplo 5x3.
Luego vas haciendo parejas según los cruces en la matriz y los vas recorriendo diagonamente.
(Se recorren diagonalmente, porque si el A1 juega con B1, A1 no puede jugar con nadie mas esa jornada)

Eemplo visual

Lista 1 (1,2,3,4,5)
Lista 2 (A,B,C)

  12345
A \
B  \
C   \
A1, B2, C3

  12345
A    \
B     \
C \
A4, B5, C1

  12345
A  \
B   \
C    \
A2, B3, C4

  12345
A     \
B  \
C   \
A5, B1, C2

etc.

La idea es que elijas el primer y saltes uno a la derecha y uno abajo para elegir el siguiente.
Si te pasas de longitud, en una de las dos direcciones vuelves al primer elemnto.

Código Delphi [-]
maxx=5
maxy=3
siguiente(x,y)
begin
   x=x+1
   y=y+1
   if (x>maxx) x=1
   if (yZmaxy) y=1
end

Al final tendrás las 15 parejas, pero debes tener en cuenta que n (la cantidad de estadios de futbol) no puede ser mayor que la cantidad de equipos en la lista más pequeña.
De lo contrario, según el ejemplo anterior algún equipo deberá jugar dos veces ese día:
A1,B2,C3,¡¡¡A4!!!

También tendrás que tener en cuenta que para que un equipo no descanse más de dos jornadas, deberá haber un número mínimo de campos.
En el ejemplo de 3x5 n debe ser >=2

[fidel]

Si en 1ª hay 5 equipos, en 2ª hay 3 equipos, y hay 2 campos, un equipo de primera tiene obligatoriamente que descansar 2 jornadas seguidas.

Podrías hacer esto

Ejemplo
Equipos primera: 1 2 3
Equipos segunda: A B C

Tabla PARTIDOS con dos campos: LOCAL, VISITANTE.
Calculas el número de partidos (en el ejemplo 3 x 3 = 9)
Añades 9 registros
Pones como local los 3 equipos de primera hasta llenar los 9 registros.

LOCAL
1
2
3
1
2
3
1
2
3

Otra tabla PROVISIONAL con 9 registros y la llenas con los equipos de segunda repitiéndolos las veces que haga falta

A
B
C
A
B
C
A
B
C

Ahora tendrías que ir cogiendo el primer equipo de la tabla provisional y ponerle como visitante en la tabla PARTIDOS y borrarle.
Coger de nuevo el primero (será otro) y ponerle de visitante en el siguiente registro y después borrarle. Esto habiendo controlado antes que esa pareja no esta ya hecha, en cuyo caso en vez del primero se coge el siguiente hasta que sea valido para no repetir pareja, cuando sea válido se coloca y se borra.
De nuevo se coge el primero el primero, etc, etc hasta que quede vacía la talbla provisional y completados los partidos.

quedaría así

LOCAL VISITANTE
1 A
2 B
3 C
1 B
2 A
3 A
1 C
2 C
3 B

Ahora ir cogiendo por orden para cada jornada, controlando que no entre un equipo repetido en la misma jornada

Si hay dos campos quedaría

joranda 1ª ... 1 A y 2 B
joranda 2ª ... 3 C y 1 B
joranda 3ª ... 2 A y 1 C
joranda 4ª ... 3 A y 2 C
joranda 5ª ... 3 B

pero ahora que he acabado veo que tampoco funciona bien pues el B y el 1 han estado dos jornadas descansando.
Mira a ver si puedes depurarlo y que funcione bien.

[Rioja72]

Muchas gracias, voy a coger la idea de los dos (duilioisola, fidel), aquí no tengo compilador para poder probarlo ahora mismo.
Crearé una matriz para los partidos de dos dimensiones que se irán marcando conforme se juegue. Para cada jornada recorreré la matriz en diagonales, por otra parte tendré dos listas ordenadas con el nº de veces que ha descansado cada equipo e iré cogiendo los primeros que aparezcan en esas listas y así hasta que quede completada la matriz. Creo que de esta forma no será necesario implementar un "vuelta atrás", que sinceramente, para este caso no sabría ni por donde empezarlo.

[ecfisa]

Hola Rioja72.

Para sumar alguna idea te pongo un código que hasta donde probé funciona.
Dados los datos, genera todas las combinaciones posibles, aunque no necesariamente en el órden que mostras en tu ejemplo.
La cantidad de elementos de las listas, así como el número de elementos por grupos se ajustan con tres SpinEdits.
Te quedaría probarlo más a fondo y ver si te puede servir. (o al menos espero que te aporte alguna idea)

Código Delphi [-]
type
  TForm1 = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    SpinEditLstA: TSpinEdit; 
    SpinEditLstB: TSpinEdit; 
    SpinEditNGrp: TSpinEdit;
    StringGrid1: TStringGrid;
    btMostrar: TButton;
    procedure FormShow(Sender: TObject);
    procedure btMostrarClick(Sender: TObject);
    procedure FormClose(Sender: TObject; var Action: TCloseAction);    
  private
    MAXLSTA, MAXLSTB: Integer;
    FGrupoA, FGrupoB, FParejas: Tstrings;
    procedure Inicializar;
    procedure Mostrar(NElem: Integer);
  public
  end;

var
 Form1: TForm1;

implementation {$R *.dfm}

procedure TForm1.FormShow(Sender: TObject);
begin
  // Crear Listas;
  FGrupoA:= TStringList.Create;
  FGrupoB:= TStringList.Create;
  FParejas:= TStringList.Create;
end;

procedure TForm1.Inicializar;
var
  c,f,x: Integer;
begin
  // Vaciar listas
  FGrupoA.Clear;
  FGrupoB.Clear;
  FParejas.Clear;
  // Ajustar base 0
  MAXLSTA:= SpinEditLstA.Value-1;
  MAXLSTB:= SpinEditLstB.Value-1;
  // Inicializar valores
  for x:= 0 to MAXLSTA do
    FGrupoA.Add('A'+IntToStr(x+1));
  for x:= 0 to MAXLSTB do
    FGrupoB.Add('B'+IntToStr(x+1));
  // Hacer los pares
  for f:= 0 to MAXLSTA do
  begin
    x:= f;
    for c:= 0 to MAXLSTB  do
    begin
      if x < MAXLSTA then
        Inc(x)
      else
        x:= 0;
      FParejas.Add(FGrupoA[x]+' '+FGrupoB[c]);
    end;
  end;
end;

procedure TForm1.Mostrar(NElem: Integer);
var
  i,j,NGrp,ix: Integer;
begin
  // Inicializar valores
  Inicializar; 
  // Limpiar StringGrid
  for i:= 0 to 10 do
    for j:= 0 to 10 do
      StringGrid1.Cells[i,j]:= '';
  // Obtener Nro de grupos
  NGrp:= (FParejas.Count) div NElem;
  for ix:= 1 to NGrp do
    StringGrid1.Cells[ix,0]:= 'Grupo '+IntToStr(ix);
  // Distribuir parejas
  ix:= 0;
  for i:= 1 to NGrp do
   for j:= 1 to NElem do
   begin
     StringGrid1.Cells[i,j]:= FParejas[ix];
     Inc(ix);
   end;
   // Si sobran elementos, agregar parejas faltantes
  ix:= FParejas.Count-(NGrp*NElem);
  if ix > 0 then
  begin
    StringGrid1.Cells[NGrp+1,0]:= 'Grupo ' + IntToStr(NGrp+1);
    for i:= 0 to ix - 1 do
      StringGrid1.Cells[NGrp+1, i+1]:= FParejas[FParejas.Count-ix+i];
  end;
end;

procedure TForm1.btMostrarClick(Sender: TObject);
begin
  Mostrar(SpinEditNGrp.Value);
end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
begin
  // Liberar TStrings
  FGrupoA.Free;
  FGrupoB.Free;
  FParejas.Free;
end;
end.

Saludos.

[Rioja72]

¡¡¡ qué pasada !!!, muchas gracias, claro que sirve de ayuda, me basaré ya en este código para continuar y depurarlo. Hay que decir que descansan más de una jornada y hay que ajustar la rejilla (grilla) para ver todos los resultados. Sigo dándole vueltas y me parece que del "vuelta atrás (backtracking)" no me salva nadie.

De nuevo, muchas gracias por tu interés.