Diagrama de Venn Celdas

12

Dados conjuntos múltiples, por ejemplo s1={2,3,7}, s2={1,2,4,7,8}y s3={4,7}, un diagrama de Venn visualiza cada conjunto mediante una curva cerrada y establece elementos que están dentro o fuera del perímetro de la curva, dependiendo de si son elementos del conjunto o no. Como todos los elementos del conjunto aparecen solo una vez en el diagrama de Venn, las curvas que representan cada conjunto deben superponerse si hay un elemento presente en más de un conjunto. Llamamos a cada uno de estos superpuestos una celda del diagrama de Venn.

Esta explicación puede ser un poco confusa, así que echemos un vistazo a un ejemplo.

Ejemplo

Un diagrama de Venn para conjuntos s1, s2y s3podría verse así:

Las células de este diagrama de Venn se (leen de arriba a abajo, de izquierda a derecha) {1,8}, {2}, {7}, {4}, {3}, {}y {}.

En la práctica, comúnmente se encuentran solo diagramas de Venn de dos o tres conjuntos, porque la representación de los diagramas de Venn de cuatro o más conjuntos no es muy clara. Sin embargo, existen, por ejemplo, para seis conjuntos:

CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1472309

La tarea

Dado un conjunto no vacío de conjuntos de enteros positivos en cualquier representación razonable, devuelva el conjunto de celdas del diagrama de Venn de los conjuntos de entrada. Específicamente, no se necesita una representación gráfica.

  • Puede escribir un programa completo o una función.
  • Puede devolver tantos conjuntos vacíos como celdas vacías (es decir, una lista de todas las celdas) en lugar de solo un conjunto vacío (es decir, el conjunto de celdas).
  • Algunas formas razonables de entrada para el ejemplo de arriba incluyen, pero no se limitan a {{2,3,7},{1,2,4,7,8},{4,7}}, [[2,3,7],[1,2,4,7,8],[4,7]], "2,3,7;1,2,4,7,8;4,7"o "2 3 7\n1 2 4 7 8\n4 7". Si tiene dudas sobre si el formato de entrada elegido es aceptable, no dude en preguntar en un comentario.
  • Su formato de salida debe coincidir con su formato de entrada, si es posible. Tenga en cuenta que esta regla requiere que su formato pueda mostrar conjuntos vacíos sin ambigüedad.
  • Este es el , así que trate de usar la menor cantidad de bytes posible en el idioma que elija. Para alentar la competencia por idioma en lugar de entre idiomas, no aceptaré una respuesta.

Casos de prueba

Aquí hay algunas entradas junto con posibles salidas:

input -> output
{{2,3,7},{1,2,4,7,8},{4,7}} -> {{1,8},{2},{7},{4},{3},{}} (or {{1,8},{2},{7},{4},{3},{},{}})
{{1,2,3},{4,5,6},{7,8,9}} -> {{1,2,3},{4,5,6},{7,8,9},{}}
{{}} -> {{}}
{{1,2,3},{1,2}} -> {{1,2},{3},{}}
{{4,3,8},{1,2,9,3},{14,7,8,5},{6,11,3,8},{10},{9,4,3,7,10}} -> {{6,11},{10},{4},{3},{8},{5,14},{1,2},{9},{7},{}}
{{2,3,4,7},{},{1,3,7,5,6},{2,3,7,5},{7,2,4,3,6},{1,4,5}} -> {{},{4},{2},{7,3},{1},{6},{5}}
{{1,2,3,4},{1,2,5,6},{1,3,5,7}} -> {{4},{3},{2},{1},{6},{5},{7}}
Laikoni
fuente
Supongo que esto es cierto debido a la definición de un conjunto, pero ¿podemos suponer que no habrá duplicados dentro de uno de los subconjuntos?
HyperNeutrino
@Hyper Neutrino Sí, puede asumir que todos los conjuntos están libres de duplicados.
Laikoni
Quizás podría agregar un caso de prueba donde ninguna de las celdas esté vacía. Por ejemplo, {{1,2,3,4}, {1,2,5,6}, {1,3,5,7}}.
Ørjan Johansen
¿Cómo no da el segundo {{1,2,3},{4,5,6},{7,8,9},{},{},{},{}}?
Leaky Nun
1
@carusocomputing Tras una inspección más cercana, encontrará que este no es un verdadero diagrama de Venn porque faltan algunas posibles superposiciones.
Laikoni

Respuestas:

8

Haskell , 71 bytes

Una función anónima que toma una lista de listas de enteros y devuelve una lista similar.

Usar como (foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[])[[1,2,3],[1,2]].

import Data.List
foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[]

Pruébalo en línea!

Cómo funciona

  • Utiliza las operaciones de tipo conjunto \\(diferencia) y intersectde Data.List.
  • Dobla la lista de "conjuntos" (representados como listas) en una lista de celdas, comenzando con la lista vacía [].
  • xes el conjunto actual que se agregará al diagrama y res la lista de celdas ya construidas.
    • x\\(id=<<r)es el subconjunto de elementos xque no se encuentran en ninguna de las celdas ya construidas.
    • [intersect x,(\\x)]<*>rdivide cada celda rsegún si sus elementos están dentro xo no.
  • Definitivamente no intenta fusionar celdas vacías, por lo que hay bastantes en la salida.
Ørjan Johansen
fuente
La misma idea que mi implementación, pero dos bytes más cortos. ¡Bien hecho!
Laikoni
4

Jalea , 14 17 bytes

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€

Pruébalo en línea!

Envío de funciones (porque el formato en el que Jelly imprime las listas por defecto no es de ida y vuelta, no puede leer su propio formato de salida, sino que una función entra y sale en el mismo formato). El enlace TIO contiene un pie de página que ejecuta la función e imprime su salida en el mismo formato en que se analiza la entrada.

Explicación

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€
FṀ‘               Find the largest number that appears in any of the input sets, + 1
   ³ þ            For each number from 1 to that number, and each of the input sets
    i ¬             find whether the number is missing from the set
       Ḅ          Convert the list of missing sets into a single number using binary
         ;        Append
        µ ṀḶ$     all numbers from 0 to the maximum value minus 1
             Ġ    Group indexes by values
              ṖṖ€ Delete the last group and last element of other groups

El requisito de que generemos al menos un conjunto vacío si no se usan todas las secciones del diagrama de Venn logra ocupar más de la mitad del programa aquí (es responsable de eso, se asegura de que tengamos al menos un grupo para elementos que no coincidan, lo que nos permite para realizar un seguimiento de cuántos conjuntos había originalmente, más los últimos nueve bytes del código fuente, excepto el Ġ). La forma básica en que lo implementamos es asegurarnos de que todos los subconjuntos del diagrama de Venn 2 ^ n tengan al menos una entrada, agregando una entrada ficticia que llene la sección "sin conjuntos" y (más adelante) una entrada ficticia para cada otra sección, luego Ġgenerará un grupo para cada subconjunto, que podemos eliminar usando ṖṖ€.


fuente
Um, no hay restricciones para un máximo de 7 series, y uno de los casos de prueba tiene más.
Ørjan Johansen
Supuse que el conjunto original tenía una longitud 3, porque así es como funcionan los diagramas de Venn, pero aparentemente no. En ese caso, quizás necesito una forma diferente de agregar el conjunto vacío solo si no se rellenan todas las secciones del diagrama de Venn. Esa es una especie de mancha desagradable en lo que de otra manera sería una pregunta bastante elegante.
Bueno, podría reemplazar 7 por 2 ^ n-1, supongo.
Ørjan Johansen
Encontré una manera de obtener el valor 2 ^ n-1 que coincide con la especificación, pero es dolorosamente largo. Esperemos que haya un camino más corto, pero aun así, esta pregunta es frustrante.
4

Perl 5, 79 bytes

sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h}

Toma información como una lista de matrices anónimas como ([2,3,7], [1,2,4,7,8], [4,7]). Produce un hash donde las claves son etiquetas y los valores son matrices anónimas correspondientes a los conjuntos de salida.

Como parte de un programa completo:

*x=
sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h};
%x=x([2,3,7],[1,2,4,7,8],[4,7]);
print"Set $_:@{$x{$_}}\n"for keys%x;

Explicación:

Da a cada conjunto un número entero como una etiqueta, $.. Crea un hash que almacena un número entero para cada elemento único $_. Agrega 2**$.para cada conjunto que $_aparece en, haciendo efectivamente un mapa binario que muestra en qué conjuntos aparece cada elemento. Finalmente, crea una matriz anónima para cada celda del diagrama de Venn y empuja los elementos que aparecen en los conjuntos correspondientes a la matriz. Entonces, cada elemento de cada matriz existe en los mismos conjuntos y, por lo tanto, en la misma celda del diagrama de Venn.

Chris
fuente
3

Pyth , 11 bytes

m-@Fds-Qdty

Banco de pruebas.

Cómo funciona

Cada región del diagrama de Venn representa elementos que están en [ciertas combinaciones de los conjuntos] pero no en [los otros conjuntos].

Entonces, generamos todas las combinaciones posibles (y eliminamos las combinaciones vacías) al encontrar el conjunto de potencia de la entrada.

Para cada combinación generada, encontramos la intersección de los conjuntos en la combinación y filtramos los elementos que están en los otros conjuntos.

m-@Fds-Qdty  input as Q
          y  power set
         t   remove the first one (empty combination)
m            for each combination d:
  @Fd            find the intersection of all the sets in d
 -               filter out those who are in
     s               the union of
      -Qd            the sets not in the combination
                     (input minus combination)
Monja permeable
fuente
2

JavaScript (ES6), 123 bytes

a=>a.map((b,i)=>b.map(e=>m[e]|=1<<i),m=[])&&[...Array(1<<a.length)].map((_,i)=>m.map((e,j)=>e==i&&j).filter(j=>j)).slice(1)
Neil
fuente