Aquí tengo los números enteros 1:7de cuatro particiones diferentes, es decir, {1}, {2,3,4}, {5,6} y {7} y esas particiones están inscritos en una lista, es decir, list(1,c(2,3,4),c(5,6),7). Trato las particiones como conjuntos, de modo que la permutación diferente de elementos dentro de una partición se reconozca como la misma. Por ejemplo, list(1,c(2,3,4),c(5,6),7)y list(7,1,c(2,3,4),c(6,5))son equivalentes.
Tenga en cuenta que no hay repetición de elementos en la lista, por ejemplo, no list(c(1,2),c(2,1),c(1,2)), ya que este problema está discutiendo particiones exclusivas en todo el conjunto.
Enumeré algunas de las diferentes permutaciones en la lista a lstcontinuación
lst <- list(list(1,c(2,3,4),c(5,6),7),
list(c(2,3,4),1,7,c(5,6)),
list(1,c(2,3,4),7,c(6,5)),
list(7,1,c(3,2,4),c(5,6)))
y lo que quiero hacer es verificar que todas las permutaciones sean equivalentes. En caso afirmativo, obtenemos el resultado TRUE.
Lo que hice hasta ahora es para ordenar los elementos dentro de cada partición, y se utiliza setdiff()con interset()y union()para juzgarlo (ver mi código de abajo)
s <- Map(function(v) Map(sort,v),lst)
equivalent <- length(setdiff(Reduce(union,s),Reduce(intersect,s),))==0
Sin embargo, supongo que este método sería lento siempre que el tamaño de la partición aumente. ¿Hay algún enfoque más rápido para hacerlo? Apreciado de antemano!
- algunos casos de prueba (datos de tamaño pequeño)
# should return `TRUE`
lst1 <- list(list(1,c(2,3,4),c(5,6)),
list(c(2,3,4),1,c(5,6)),
list(1,c(2,3,4),c(6,5)))
# should return `TRUE`
lst2 <- list(list(1:2, 3:4), list(3:4, 1:2))
# should return `FALSE`
lst3 <- list(list(1,c(2,3,4),c(5,6)), list(c(2,3,4),1,c(5,6)), list(1,c(2,3,5),c(6,4)))
fuente
Mapllamadas múltipleslst_equal = list(list(1:2, 3:4), list(3:4, 1:2))y también uno donde el resultado debería serFALSE, tal vezlst_false <- list(list(1,c(2,3,4),c(5,6)), list(c(2,3,4),1,c(5,6)), list(1,c(2,3,5),c(6,4)))FALSE. De esa manera, cuando una respuesta funciona en algunos casos de prueba, pero no en todos, es fácil diagnosticar por qué. Cuando solo hay un solo ejemplo, pierdes matices en los resultados de la prueba. También es bueno agregar nuevos ejemplos en lugar de cambiar los ejemplos existentes en personas que ya han trabajado en ellos.lstes potencialmente larga, podría ganar eficiencia con otros enfoques. Por ejemplo, una primera verificación quelength(unique(lengths(lst))) == 1regresaría muy rápidamenteFALSEsi alguna de las listas internas tiene el número incorrecto de elementos ...lst, al compararlst[[i]]alst[[1]], y de esa manera se puede parar tan pronto como se encuentra una falta de coincidencia, en lugar de hacer todas las comparaciones. Silstes largo yFALSEs son comunes, esto podría ser una gran ganancia de eficiencia, pero probablemente no valga la pena de otra manera.Respuestas:
Una publicación sobre
Ry cualquier variante de rápido no está completa sin una solución con rcpp .Para maximizar la eficiencia, elegir la estructura de datos correcta será de suma importancia. Nuestra estructura de datos necesita almacenar valores únicos y también tener inserción / acceso rápido. Esto es exactamente lo que encarna std :: unordered_set . Solo necesitamos determinar cómo podemos identificar de forma única cada uno
vectorde los desordenadosintegers.Introduzca el teorema fundamental de la aritmética
El TLC establece que cada número puede ser representado de manera única (hasta el orden de los factores) por el producto de números primos.
Aquí hay un ejemplo que demuestra cómo podemos usar el TLC para descifrar rápidamente si dos vectores son equivalentes hasta el orden (NB a
Pcontinuación es una lista de números primos ...(2, 3, 5, 7, 11, etc.):A partir de esto, vemos eso
vec1yvec3correlacionamos correctamente con el mismo número, mientras quevec2se asigna a un valor diferente.Dado que nuestros vectores reales pueden contener hasta cien enteros menores que 1000, la aplicación del TLC producirá números extremadamente grandes. Podemos evitar esto aprovechando la regla del producto del logaritmo:
Con esto a nuestra disposición, podremos abordar ejemplos de números mucho más grandes (Esto comienza a deteriorarse en ejemplos extremadamente grandes).
Primero, necesitamos un generador de números primos simple (NB En realidad estamos generando el registro de cada número primo).
Y aquí está la implementación principal:
Aquí están los resultados cuando los aplica
lst1, lst2, lst3, & lst (the large one)@GKi.Y aquí hay algunos puntos de referencia con el
unitsparámetro establecido enrelative.Aproximadamente 3 veces más rápido que la solución más rápida hasta ahora en el ejemplo más grande.
Para mí, este resultado dice mucho de la belleza y la eficiencia de lo
base Rque muestran @GKi, @ chinsoon12, @Gregor, @ThomasIsCoding y más. Escribimos alrededor de 100 líneas muy específicasC++para obtener una velocidad moderada. Para ser justos, lasbase Rsoluciones terminan llamando principalmente código compilado y terminan utilizando tablas hash como lo hicimos anteriormente.fuente
Después de ordenar puedes usar
duplicatedyall.Alternativa: ordenar en un bucle
Alternativa: ordenar durante el ciclo y permitir la salida anticipada
o usando
setequalo mejorando ligeramente la idea de @ chinsoon12 para intercambiar la lista con un vector!
o evitar el segundo
ordero intercambiar
orderconmatch(ofmatch)O sin salida anticipada.
o escrito en C ++
¡Gracias a @Gregor por sugerencias para mejorar la respuesta!
fuente
lst <- list(list(1,c(2,3,4),c(5,6),7), list(c(2,3,4),1,7,c(5,6)), list(1,c(2,3,4),7,c(6,5)), list(7,1,c(3,2,4),c(5,6)))será juzgado comoFALSEmin!Actuación:
Bibliotecas:
Funciones:
Datos:
fuente
length(setdiff(Reduce(union,s),Reduce(intersect,s)))==0, lo siento por mi error ....Esperemos que la segunda vez tenga suerte
Casos de prueba:
controles:
código de tiempo:
tiempos:
fuente