Combinando eficientemente combinaciones de enteros

Digamos que tenemos una matriz de 5x5, llena de ceros.

myMatrix <- matrix(rep(0, 25), ncol = 5)

Ahora, escojamos un triplete de enteros entre 1 y 5.

triplet <- c(1,2,3)

Para todas las combinaciones de este triplete ahora agregamos 1 en la matriz, con esta función:

addCombinationsToMatrix <- function(.matrix, .triplet){
    indexesToChange <- as.matrix(expand.grid(.triplet, .triplet))
    .matrix[indexesToChange] <- .matrix[indexesToChange] + 1
    .matrix
}

Usando la función, pasamos de

myMatrix

     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    0    0    0
[2,]    0    0    0    0    0
[3,]    0    0    0    0    0
[4,]    0    0    0    0    0
[5,]    0    0    0    0    0

a

myMatrix <- addCombinationsToMatrix(myMatrix, triplet)
myMatrix

     [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    1    0    0
[2,]    1    1    1    0    0
[3,]    1    1    1    0    0
[4,]    0    0    0    0    0
[5,]    0    0    0    0    0

Si elegimos otro triplete, pasamos a

nextTriplet <- 2:4
myMatrix <- addCombinationsToMatrix(myMatrix, nextTriplet)
myMatrix

     [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    1    0    0
[2,]    1    2    2    1    0
[3,]    1    2    2    1    0
[4,]    0    1    1    1    0
[5,]    0    0    0    0    0

Entonces, las combinaciones fila-columna representan la frecuencia con la que dos enteros se han mostrado juntos en un triplete: 3 y 4 se han mostrado juntos una vez, 2 y 3 se han mostrado juntos dos veces.

Pregunta : ¿Cómo se pueden elegir trillizos, de modo que cada combinación (1-2, 1-3, 1-4 ...) se recoja al menos una vez y se minimice el número de trillizos.

Estoy buscando un algoritmo aquí que elija el próximo triplete.

Idealmente se puede extender a

• matrices arbitrariamente grandes (10x10, 100x100 ...)
• vectores arbitrariamente grandes (cuadruplets, quintillizos, n-tuplets)
• un número arbitrario de veces que una combinación debe haber sido elegida al menos

Ejemplo:

myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 1:3)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, 3:5)
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(1,4,5))
myMatrix
myMatrix <- addCombinationsToMatrix(myMatrix, c(2,4,5))
myMatrix

EDITAR : Solo para estar seguro: la respuesta no tiene que ser Rcódigo. También puede ser algún otro idioma o incluso seudocódigo.

EDIT 2 : Se me ocurrió ahora, que hay diferentes formas de medir la eficiencia. En realidad quise decir que el algoritmo debería tomar la menor cantidad de iteraciones posible. El algoritmo que es rápido también es muy bueno, pero no es el objetivo principal aquí.

Gran pregunta! Esto surge en el diseño de la encuesta, donde desea algunas versiones diferentes de la encuesta, cada una de las cuales solo contiene un subconjunto de las preguntas, pero desea que cada par (o t-tupla) de preguntas se hayan formulado al menos una vez.

Esto se llama diseño de cobertura y es una variante del clásico problema de cobertura de conjunto . Como puede leer en una excelente publicación de Mathematics Stack Exchange sobre el tema, la gente usa la notación C (v, k, t) que indica el número mínimo de subconjuntos de elementos k que necesita dibujar (k = 3 en su caso) de una v conjunto de elementos (v = 5 en su caso) de modo que cada subconjunto de elementos t en todo el conjunto (t = 2 en su caso) esté contenido dentro de uno de los subconjuntos seleccionados. La gente ha evaluado esta función para muchas tuplas diferentes (v, k, t); ver, por ejemplo, https://ljcr.dmgordon.org/cover/table.html . Podemos leer de esa tabla que C (5, 3, 2) = 4, con el siguiente diseño posible:

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

En primer lugar, este problema es NP-hard, por lo que todos los algoritmos exactos conocidos se escalarán exponencialmente en las entradas v, k y t. Entonces, si bien puede resolver instancias pequeñas exactamente mediante enumeración o algún método exacto más inteligente (por ejemplo, programación de enteros), es probable que deba recurrir a métodos heurísticos a medida que el tamaño del problema sea muy grande.

Una posibilidad en esta dirección es la cobertura lexicográfica, como se propone en https://arxiv.org/pdf/math/9502238.pdf (notará que muchas de las soluciones en el sitio enlazadas anteriormente incluyen "cobertura lex" como método de construcción). Básicamente, enumera todas las k-tuplas posibles en orden lexicográfico:

123
124
125
134
135
145
234
235
245
345

Luego agrega con avidez la tupla k que cubre las tuplas t descubiertas anteriormente, rompiendo lazos utilizando el orden lexicográfico.

Así es como funciona el algoritmo en nuestro caso:

1. Al principio, cada 3 tuplas cubre 3 2 tuplas diferentes, por lo que agregamos, 123ya que es lexicográficamente más temprano.

2. Después de hacer esto, las 2 tuplas de 12, 13y 23se han cubierto, mientras que las 2 tuplas restantes no están cubiertas. Un número de 3 tuplas cubre 3 más de 2 tuplas, por ejemplo, 145y 245. Recogemos 145, ya que es la primera lexicográfico, que cubre 14, 45y 15.

3. Ahora tenemos 4 restantes descubiertas 2-tuplas - 24, 25, 34, y 35. Ninguna tupla de 3 cubre 3 de estos, pero varios cubren 2, por ejemplo, 234y 345. Seleccionamos 234como lexicográficamente los primeros.

4. Tenemos dos tuplas descubiertas restantes de 2 - 25y 35. Seleccionamos 235como la única 3-tupla que cubre ambos.

Terminamos con la solución exacta que se muestra arriba. Es importante destacar que este es solo un método heurístico: no garantiza que 4 sea el número más pequeño de 3 tuplas necesarias para cubrir todos los pares de un conjunto con 5 elementos. En este caso, un límite inferior de Schönheim (se proporciona una referencia en el artículo vinculado anteriormente) nos convence de que, de hecho, C (5, 3, 2) no puede ser menor que 4. Llegamos a la conclusión de que la solución del recubrimiento lexicográfico es De hecho óptimo.

Necesitaría un ajuste para cubrir cada t-tupla un cierto número de veces r. Una obvia sería repetir cada tupla para cubrirla "r" veces, y luego ejecutar la cobertura de lex como de costumbre (por ejemplo, en el primer paso arriba de cada 3 tuplas cubriría 9 2 tuplas con r = 3). Por supuesto, esto sigue siendo una heurística para su problema general debido al uso de cobertura lex.

Aquí hay una opción que utiliza data.tablepara realizar un seguimiento del recuento de matrices y RcppAlgosgenerar las combinaciones:

library(RcppAlgos)
library(data.table)

M <- 100 #5 #10 #100
sz <- 5 #3 #4 5 
minpick <- 3 #1 #2
d <- integer(M)

system.time({
    universe <- as.data.table(comboGeneral(M, 2L, nThreads=4L))[, count := 0L]
    ntuples <- 0
    while (universe[, any(count < minpick)]) {
        v <- universe[order(count), head(unique(c(V1[1L:2L], V2[1L:2L])), sz)]
        universe[as.data.table(comboGeneral(v, 2L, nThreads=4L)), on=.NATURAL, count := count + 1L]
        ntuples = ntuples + 1L
    }
    ntuples
})
#   user  system elapsed 
#  26.82    9.81   28.75 

m <- matrix(0L, nrow=M, ncol=M)
m[as.matrix(universe[, V1:V2])] <- universe$count
m + t(m) + diag(d)

Es un algoritmo codicioso, por lo tanto, no estoy seguro de si esto resultará en un número mínimo de tuplas.

Dado que esta pregunta solicita enfoques algorítmicos para cubrir diseños, proporcionaré uno que proporcione respuestas exactas (también conocido como el mejor diseño posible) utilizando la programación de enteros en R. Por cada k-tupla que esté considerando (k = 3 para usted, ya que está seleccionando trillizos), defina una variable de decisión que tome el valor 1 si lo incluye en su diseño y 0 si no. Entonces, en su caso, definiría x_123 para indicar si la tupla (1,2,3) está seleccionada, x_345 para (3,4,5), y así sucesivamente.

El objetivo del modelo de optimización es minimizar el número de tuplas seleccionadas, es decir, la suma de todas sus variables de decisión. Sin embargo, para cada t-tupla (t = 2 en su caso), debe incluir una variable de decisión que contenga esa t-tupla. Esto produce una restricción para cada t-tupla. Como ejemplo, tendríamos x_123+x_124+x_125 >= 1la restricción que requiere que el par 12esté en alguna tupla seleccionada.

Esto produce el siguiente modelo de optimización:

min  x_123+x_124+...+x_345
s.t. x_123+x_124+x_125 >= 1  # constraint for 12
     x_123+x_134+x_135 >= 1  # constraint for 13
     ...
     x_145+x_245+x_345 >= 1  # constraint for 45
     x_ijk binary for all i, j, k

Puede extender esto para requerir r repeticiones de cada t-tupla cambiando el lado derecho de cada desigualdad a "r" y requiriendo que todas las variables sean enteras en lugar de binarias.

Esto es fácil de resolver con un paquete como lpSolveen R:

library(lpSolve)
C <- function(v, k, tt, r) {
  k.tuples <- combn(v, k)
  t.tuples <- combn(v, tt)
  mod <- lp(direction="min",
            objective.in=rep(1, ncol(k.tuples)),
            const.mat=t(apply(t.tuples, 2, function(x) {
              apply(k.tuples, 2, function(y) as.numeric(sum(x %in% y) == tt))
            })),
            const.dir=rep(">=", ncol(t.tuples)),
            const.rhs=rep(r, ncol(t.tuples)),
            all.int=TRUE)
  k.tuples[,rep(seq_len(ncol(k.tuples)), round(mod$solution))]
}
C(5, 3, 2, 1)
#      [,1] [,2] [,3] [,4]
# [1,]    1    1    1    3
# [2,]    2    2    2    4
# [3,]    3    4    5    5
C(5, 3, 2, 3)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    1    1    1    2    2    2     3
# [2,]    2    2    2    3    3    4    3    3    4     4
# [3,]    3    4    5    4    5    5    4    5    5     5

Si bien esto resuelve su problema exactamente, no escalará bien a problemas de gran tamaño. Esto se debe a que el problema es NP-hard: ningún algoritmo exacto conocido se escalará bien. Si necesita resolver grandes instancias de problemas, entonces la heurística recomendada en otras respuestas aquí es su mejor opción. O podría resolver con programación entera (como lo hacemos aquí) y establecer un tiempo de espera; entonces trabajará con la mejor solución encontrada por su tiempo de espera, que es una solución heurística al problema en general.