qsig girona español descargar algorithm math combinatorics

algorithm - girona - qgis manual



Creando combinaciones que no tienen más un elemento de intersección. (5)

Estoy buscando crear un tipo especial de combinación en el que no haya dos conjuntos que tengan más de un elemento de intersección. Dejame explicarte con un ejemplo:

Digamos que tenemos un conjunto de 9 letras que contiene A, B, C, D, E, F, G, H y I

Si creas las combinaciones estándar de tres letras que no se repiten, tendrás conjuntos de 9C3. Estos contendrán conjuntos como ABC, ABD, BCD, etc. Busco crear conjuntos que tengan como máximo una sola letra común. Así que en este ejemplo, obtendremos los siguientes conjuntos:

ABC, ADG, AEI, AFH, BEH, BFG, BDI, CFI, CDH, CEG, DEF y GHI. Tenga en cuenta que si toma dos juegos, no hay más de 1 letra de repetición.

¿Cuál sería una buena manera de generar tales conjuntos? Debe ser una solución escalable para que pueda hacerlo con un conjunto de 1000 letras, con un tamaño de subconjunto de 4.

Cualquier ayuda es muy apreciada.

Gracias

@khuss

El mismo método puede ser generalizado. Pero no es un algoritmo lineal y puede ser exponencial.

Por ejemplo: cuando el tamaño del subconjunto es 4, seleccionamos 2 o más pares con 4 caracteres únicos.

por ejemplo, "AB y CD" o "AB, AC y AD" solo si se cumplen las siguientes condiciones:

  1. Todas las parejas formadas por los personajes de la 4-tupla están disponibles. por ejemplo, si queremos formar ABCD utilizando AB, AC y AD, entonces todos los pares creados A, B, C y D, es decir, AB, AC, AD, BC, BD, CD, todos deben estar disponibles.
  2. Si se cumple la condición 1, formamos ABCD y marcamos los pares C (4,2) = 6 como no disponibles.

Continuamos como antes hasta que no se puedan formar más 4 tuplas o no haya más pares disponibles.

Aquí hay un enfoque que satisfará los requisitos que ha indicado. Si hace lo que quieres, no lo sé.

  1. En una hoja grande de papel, dibuje una cuadrícula regular con al menos 250 cuadrados.
  2. Etiqueta los lados de los cuadrados con las letras en tu alfabeto (250 cuadrados x 4 lados == 1000).
  3. Cada cuadrado define uno de tus subconjuntos. Cada uno comparte un lado (es decir, una letra) solo con cada uno de sus (hasta) 4 vecinos. Ningún lado (es decir, la letra) es compartido por más de 2 cuadrados (subconjuntos).

Lo dejaré en manos de ustedes para convertir esto en código de trabajo, pero no creo que deba ser demasiado difícil y que deba escalar bien. Tenga en cuenta que también debería funcionar para cualquier otro tamaño de subconjunto, puede agrupar el plano con n-gons irregulares para cualquier n, aunque puede ser difícil.

El otro enfoque que pensé es:

  1. En una hoja grande de papel, dibuje N puntos, donde N es el tamaño de su alfabeto. Etiqueta cada punto con una de las letras del alfabeto.
  2. Conecte cualquier n puntos, donde n es el tamaño de los subconjuntos requeridos. Ese es tu primer subconjunto.
  3. Elija uno de los puntos ya conectados, conéctelo a (n-1) más puntos no conectados. Ese es tu próximo subconjunto.
  4. Repita el paso 3 hasta que haya terminado.

Esto requiere un poco más de contabilidad, y hay una serie de casos de esquina con los que hay que lidiar, pero de nuevo no debería ser demasiado difícil de codificar.

EDITAR: Es fácil transformar mi primer enfoque en una forma que es más obviamente un algoritmo en una gráfica. Modele cada subconjunto como un nodo, y cada letra en el alfabeto como un borde. Construya una gráfica donde cada nodo tenga un grado n (número de elementos en el subconjunto) y cada letra (borde) se use una vez.

Aquí hay un resumen del algoritmo.

  1. Primero encuentre todos los pares: AB BC CD DE EF FG GH HI AC BD CE DF EG FH GI AD BE CF DG EH FI AE BF CG DH EI AF BG CH DI AG BH CI AH BI AI

Estos se pueden almacenar en una matriz de sixe n (n-1)

  1. Ahora comience a intentar combinar pares consecutivos usando las siguientes reglas: a. Dos pares se pueden combinar solo cuando hay un personaje común. segundo. La combinación es posible cuando el par formado dejando el carácter común también está disponible. por ejemplo, si queremos combinar AB y AC, entonces debemos verificar si BC también está disponible. do. Cuando se cumplen las reglas anteriores, combinamos los dos pares en un triple (por ejemplo, AB y AC se fusionan para formar ABC) y marcamos los tres pares, como AB, AC y BC como no disponibles.

  2. Continúe haciendo esto buscando pares disponibles en la matriz y uniéndolos para formar triples y marcando los pares no disponibles hasta que no haya pares disponibles o ya no se puedan formar triples.

Ejemplo: 1. combinar AB + AC -> ABC; Mark AB, AC y BC no disponibles. 2. combinar AD + AE -> AED; Marca AD, AE y DE no disponible. 3. combinar AF + AG -> AFG; Mark AF, AG y FG no disponibles. ..

Tuve que agregar otra respuesta ya que la otra ya era demasiado larga.

Si tiene las siguientes restricciones:

1) Necesitas grupos de 4 todas las semanas.

2) Cada grupo en una semana determinada está separado y cada estudiante está en exactamente un grupo.

3) Si dos estudiantes están en el mismo grupo, no deben estar en el mismo grupo en el futuro.

Si construyes una gráfica G de la siguiente manera:

1) Cada alumno es un nodo.

2) Dos estudiantes se unen con una ventaja si no han estado juntos en un grupo antes.

¡Con los estudiantes que abandonan / se unen arbitrariamente, esto se convierte en un problema difícil! Aunque empieces con una gráfica completa inicialmente, después de algunas semanas, la gráfica podría volverse bastante impredecible.

Su problema: debe encontrar un subgrafo que abarque G, de manera que sea una unión de copias de K_4 o, en otras palabras, una partición en K_4s.

Desafortunadamente, parece que este problema es NP-Duro: la cobertura exacta por 4 juegos (que es NP-Completa) puede reducirse a su problema (al igual que la cobertura Exact por 3 juegos se puede reducir a la partición en triángulos).

Quizás esto ayude a dar algunos algoritmos de aproximación: http://www.siam.org/proceedings/soda/2010/SODA10_122_chany.pdf

(Su problema se puede reducir a la coincidencia de Hypergraph y, por lo tanto, se pueden usar algoritmos para eso).

Cubierta exacta: http://en.wikipedia.org/wiki/Exact_cover

Partición en triángulos: https://noppa.tkk.fi/noppa/kurssi/t-79.5103/viikkoharjoitukset/T-79_5103_solutions_5.pdf

Cobertura exacta por 4 conjuntos = Dado un conjunto S de tamaño 4m y una colección C de subconjuntos de 4 elementos de S, ¿existe un subconjunto C ''de C, de manera que cada elemento de S aparezca exactamente una vez en C''?

Desafortunadamente, parece que es posible que tengas que cambiar algunas restricciones.

Digamos que tienes n letras (o estudiantes, o lo que sea), y cada semana quieres dividirlas en subconjuntos de tamaño k (para un total de n/k subconjuntos cada semana). Este método generará casi n/k subconjuntos cada semana; a continuación se muestra cómo extenderlo para generar exactamente n/k subconjuntos.

Generando los subconjuntos (sin particiones)

Primero escoge p, el primo más grande <= n / k.

Consideremos cada par ordenado (a, b) tal que

0 <= a < k 0 <= b < p

Podemos mapear cada pareja a una de nuestras cartas; por lo tanto, podemos asignar p*k <= n letras de esta manera (nuevamente, muestro a continuación cómo mapear exactamente n letras)

(0,0) => ''A'' (0,1) => ''B'' ... (0,p-1) => ''F'' (1,0) => ''G'' (1,1) => ''H'' ... (k-1,p-1) => ''s''

Ahora, dado

0 <= w < p 0 <= i < p

Podemos crear un conjunto S w (i) de nuestros pares ordenados. Cada emparejamiento en Sw (i) representará una letra (de acuerdo con nuestra asignación anterior), y el conjunto Sw (i) en sí mismo representa una "agrupación de letras" alias. un subconjunto de tamaño k.

La fórmula para S w (i) es

Sw(i) = {(0,i mod p), (1,(w+i) mod p), (2,(2w+i) mod p),..., ((k-1),((k-1)*w+i) mod p)} = { (x,y) | 0 <= x < k and y = w*x + i (mod p)}

Si variamos w e i sobre todos los valores posibles, obtenemos p 2 conjuntos totales. Cuando tomemos dos de estos conjuntos, tendrán como máximo un elemento de intersección.

Cómo funciona

Digamos que tenemos dos conjuntos S w1 (i 1 ) y S w2 (i 2 ). Si S w1 (i 1 ) y S w2 (i 2 ) tienen más de un elemento en común, entonces existen al menos dos x tales que

w1*x + i1 = w2*x + i2 (mod p) (w1-w2)*x + (i1-i2) = 0 (mod p)

Sin embargo, cualquiera que haya tomado aritmética modular sabe que si p es primo, x tiene una solución única o (w 1 = w 2 e i 1 = i 2 ); por lo tanto, no puede haber más de una x, y S w1 (i 1 ) y S w2 (i 2 ) pueden tener como máximo un elemento de intersección.

Análisis

Dado que p < n/k , según el teorema de Chebyshev (que establece que hay un número primo entre x y 2x para x> 3)

n/2k < p <= n/k

Por lo tanto, este método genera al menos (n / 2k) 2 subconjuntos de letras, aunque en la práctica p estará más cerca de n / k, por lo que el número estará más cerca de (n / k) 2 . Dado que un límite superior simple para el máximo posible de tales subconjuntos es n(n-1)/(k(k-1)) (vea el comentario de BlueRaja a continuación), esto significa que el algoritmo es asintóticamente óptimo y generará cerca de la cantidad óptima de conjuntos (incluso en el peor de los casos, no generará menos de aproximadamente 1/4 de la cantidad óptima; vea nuevamente el comentario a continuación)

Partición

Ahora desea agrupar las letras en particiones cada semana: cada semana, todas las letras se incluyen en exactamente un grupo.
Hacemos esto al dejar que w se fije a un cierto valor (que representa la semana) y al permitir que varíe de 0 a p-1.

Prueba

Considere los grupos que creamos:

Sw(i) = { (x,y) | 0 <= x < k and y = w*x + i (mod p)}

Digamos que w es fijo y que varía de 0 a p-1. Entonces obtenemos p sets:

Sw(0), Sw(1), ..., Sw(p-1)

Ahora digamos que S w (i 1 ) y S w (i 2 ) (con i 1 = / = i 2 ) se intersecan; entonces

w*x + i1 = w*x + i2 (mod p)

para algunos x, y por lo tanto i 1 = i 2 . Por lo tanto, S w (i 1 ) y S w (i 2 ) no se intersecan.

Como no se intersectan dos de nuestros conjuntos, y hay exactamente p de ellos (cada uno con k elementos), nuestros conjuntos forman una partición de las letras k * p.

Generando n / k subconjuntos cada semana

La mayor desventaja de este método es que genera conjuntos para p * k letras, en lugar de n letras. Si las últimas letras no se pueden omitir (como en su caso, donde las letras son estudiantes), hay dos formas de generar exactamente n / k subconjuntos cada semana:

  1. Encuentre un conjunto de números primos p 1 , p 2 , p 3 , ... que suma exactamente n / k. Luego podemos tratar cada grupo de letras p i k como un alfabeto independiente, de modo que en lugar de encontrar subconjuntos de letras p k, encontramos un grupo de subconjuntos para letras p 1 * k, otro grupo de subconjuntos para letras p 2 * k , otro grupo...
    Esto tiene la desventaja de que las letras de un grupo nunca se emparejarán con las letras de otro grupo, reduciendo el número total de subconjuntos generados. Afortunadamente, si n es par, por la conjetura de Goldbach †, solo necesitarás dos grupos como máximo (si n es impar, solo necesitarás tres como máximo )
    Este método garantiza subconjuntos de tamaño k, pero no genera tantos subconjuntos.
    † Aunque no se ha comprobado, se sabe que es cierto para todos los números ridículamente grandes que probablemente encuentre para este problema

  2. La otra opción es usar el primo más pequeño p> = n / k. Esto le dará p * k> = n letras: después de que se hayan generado los subconjuntos, simplemente tire las letras adicionales. Por lo tanto, al final, esto le da algunos subconjuntos con tamaño <k. Suponiendo que k divide n uniformemente (es decir, n / k es un número entero), podría tomar los subconjuntos más pequeños y mezclarlos a mano para hacer subconjuntos de tamaño k, pero corre el riesgo de que se superponga con los subconjuntos pasados ​​/ futuros de esta manera.
    Este método genera al menos tantos subconjuntos como el método original, pero algunos pueden tener un tamaño <k

Ejemplo

Tome n = 15, k = 3. es decir, hay 15 estudiantes y estamos haciendo grupos de tres.

Para empezar, seleccionamos la mayor p <= n / k. n / k es primo (¡afortunados nosotros!) , entonces p = 5.

Asignamos a los 15 estudiantes en los pares ordenados (a, b) descritos anteriormente, que nos proporcionan (cada letra es un estudiante):

(0,0) = A (0,1) = B (0,2) = C (0,3) = D (0,4) = E (1,0) = F (1,1) = G (1,2) = H (1,3) = I (1,4) = J (2,0) = K (2,1) = L (2,2) = M (2,3) = N (2,4) = O

El método genera 25 grupos de tres. Por lo tanto, como tenemos que programar n / k = 5 grupos cada semana, podemos programar 5 semanas de actividades (5 grupos por semana * 5 semanas = 25 grupos).

Para la semana 0, generamos la partición como

S0(i), for i = 0 to 4. S0(0) = { (0,0), (1,0), (2,0) } = AFK S0(1) = { (0,1), (1,1), (2,1) } = BGL S0(2) = { (0,2), (1,2), (2,2) } = CHM S0(3) = { (0,3), (1,3), (2,3) } = DIN S0(4) = { (0,4), (1,4), (2,4) } = EJO

Para la semana 4 será

S4(i) for i = 0 to 4. S4(0) = { (0,0), (1, (4*1 + 0) mod 5), (2, (2*4 + 0) mod 5) } = { (0,0), (1,4), (2,3) } = AJN S4(1) = { (0,1), (1, (4*1 + 1) mod 5), (2, (4*2 + 1) mod 5) } = { (0,1), (1,0), (2,4) } = BFO S4(2) = { (0,2), (1, (4*1 + 2) mod 5), (2, (4*2 + 2) mod 5) } = { (0,2), (1,1), (2,0) } = CGK S4(3) = { (0,3), (1, (4*1 + 3) mod 5), (2, (4*2 + 3) mod 5) } = { (0,3), (1,2), (2,1) } = DHL S4(4) = { (0,4), (1, (4*1 + 4) mod 5), (2, (4*2 + 4) mod 5) } = { (0,4), (1,3), (2,2) } = EIM

Aquí está el calendario para las 5 semanas:

Week: 0 S0(0) ={(0,0) (1,0) (2,0) } = AFK S0(1) ={(0,1) (1,1) (2,1) } = BGL S0(2) ={(0,2) (1,2) (2,2) } = CHM S0(3) ={(0,3) (1,3) (2,3) } = DIN S0(4) ={(0,4) (1,4) (2,4) } = EJO Week: 1 S1(0) ={(0,0) (1,1) (2,2) } = AGM S1(1) ={(0,1) (1,2) (2,3) } = BHN S1(2) ={(0,2) (1,3) (2,4) } = CIO S1(3) ={(0,3) (1,4) (2,0) } = DJK S1(4) ={(0,4) (1,0) (2,1) } = EFL Week: 2 S2(0) ={(0,0) (1,2) (2,4) } = AHO S2(1) ={(0,1) (1,3) (2,0) } = BIK S2(2) ={(0,2) (1,4) (2,1) } = CJL S2(3) ={(0,3) (1,0) (2,2) } = DFM S2(4) ={(0,4) (1,1) (2,3) } = EGN Week: 3 S3(0) ={(0,0) (1,3) (2,1) } = AIL S3(1) ={(0,1) (1,4) (2,2) } = BJM S3(2) ={(0,2) (1,0) (2,3) } = CFN S3(3) ={(0,3) (1,1) (2,4) } = DGO S3(4) ={(0,4) (1,2) (2,0) } = EHK Week: 4 S4(0) ={(0,0) (1,4) (2,3) } = AJN S4(1) ={(0,1) (1,0) (2,4) } = BFO S4(2) ={(0,2) (1,1) (2,0) } = CGK S4(3) ={(0,3) (1,2) (2,1) } = DHL S4(4) ={(0,4) (1,3) (2,2) } = EIM

Ejemplo más práctico

En su caso, n = 1000 estudiantes y k = 4 en cada grupo. Por lo tanto, seleccionamos p como el primo más grande <= (n / k = 1000/4 = 250), así que p = 241. Sin considerar las alteraciones anteriores en "Generar n / k subconjuntos cada semana" , este método generará una programación Para 961 estudiantes con duración de 241 semanas.

(Un límite superior para el número máximo de subconjuntos posible sería 1000 * 999 / (4 * 3) = 83250, aunque el número real es probablemente menor que eso. Aun así, este método genera 58081 subconjuntos, o aproximadamente el 70% de el máximo teórico!)

Si usamos el primer método anterior para generar un horario para exactamente 1000 estudiantes, tomamos p 1 = 113, p 2 = 137 (de modo que p 1 + p 2 = n / k). Por lo tanto, podemos generar (113) ^ 2 + (137) ^ 2 = 31,538 subconjuntos de estudiantes, lo suficiente para durar 113 semanas.

Si usamos el segundo método anterior para generar un horario para exactamente 1000 estudiantes, tomamos p = 251. Esto nos dará un horario para 1004 estudiantes por 251 semanas; eliminamos a los 4 estudiantes fantasma del horario cada semana. Generalmente, esto resultará en cuatro grupos de 3 cada semana (aunque es poco probable, también es posible tener, por ejemplo, un grupo de 2 y dos grupos de 3). Los grupos con <4 estudiantes siempre tendrán un número total de múltiples de 4, por lo que puede colocarlos manualmente en grupos de 4, con el riesgo de potencialmente tener dos de esos estudiantes juntos más tarde en otro grupo.

Pensamientos finales

Un defecto de este algoritmo es que no es realmente flexible: si un estudiante se retira, siempre estamos atrapados con un estudiante fantasma. Además, no hay manera de agregar nuevos estudiantes a la programación a mediados del año (a menos que lo permitamos creando inicialmente estudiantes fantasmas).

Este problema cae dentro de la categoría de sistemas de conjuntos restringidos en combinatoria. Consulte este documento para obtener más información, especialmente los Capítulos 1 y 2. Como es un archivo PostScript, necesitará gsview o algo para verlo.