Venn Diagram Cells

12

Dados vários conjuntos, por exemplo s1={2,3,7}, s2={1,2,4,7,8}e s3={4,7}, um diagrama de Venn visualiza cada conjunto por uma curva fechada e por elementos do conjunto que estão dentro ou fora do perímetro da curva, dependendo de serem ou não elementos do conjunto. Como todos os elementos do conjunto aparecem apenas uma vez no digrama de Venn, as curvas que representam cada conjunto precisam se sobrepor se um elemento estiver presente em mais de um conjunto. Chamamos cada uma dessas células sobrepostas a uma célula do diagrama de Venn.

Essa explicação pode ser um pouco confusa, então vamos dar uma olhada em um exemplo.

Exemplo

Um diagrama de Venn para conjuntos s1, s2e s3poderia ser assim:

As células deste diagrama de Venn são (lidas de cima para baixo, da esquerda para a direita) {1,8}, {2}, {7}, {4}, {3}, {}e {}.

Na prática, geralmente encontramos apenas diagramas de Venn de dois ou três conjuntos, porque a representação dos diagramas de Venn de quatro ou mais conjuntos não é muito clara. Entretanto, eles existem, por exemplo, para seis conjuntos:

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

A tarefa

Dado um conjunto não vazio de conjuntos de números inteiros positivos em qualquer representação razoável, retorne o conjunto de células do diagrama de Venn dos conjuntos de entrada. Especificamente, nenhuma representação gráfica é necessária.

  • Você pode escrever um programa completo ou uma função.
  • Você pode retornar quantos conjuntos vazios houver células vazias (ou seja, uma lista de todas as células) em vez de apenas um conjunto vazio (ou seja, o conjunto de células).
  • Algumas maneiras razoáveis de entrada para o exemplo acima incluem, mas não estão limitados 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"ou "2 3 7\n1 2 4 7 8\n4 7". Em caso de dúvida se o formato de entrada escolhido é aceitável, não hesite em perguntar em um comentário.
  • Seu formato de saída deve corresponder ao seu formato de entrada, se possível. Observe que esta regra exige que seu formato seja capaz de exibir conjuntos vazios sem ambiguidade.
  • Isso é , então tente usar o mínimo de bytes possível no idioma de sua escolha. Para incentivar a competição por idioma e não entre idiomas, não aceitarei uma resposta.

Casos de teste

Aqui estão algumas entradas, além de possíveis saídas:

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
fonte
Suponho que isso seja verdade por causa da definição de um conjunto, mas podemos assumir que não haverá duplicatas em um dos subconjuntos?
HyperNeutrino
@ Hyper Neutrino Sim, você pode assumir que todos os conjuntos são duplicados gratuitamente.
Laikoni 7/17
Talvez você possa adicionar um caso de teste em que nenhuma célula esteja vazia. Por exemplo, {{1,2,3,4}, {1,2,5,6}, {1,3,5,7}}.
Ørjan Johansen
Como o segundo não dá {{1,2,3},{4,5,6},{7,8,9},{},{},{},{}}?
Freira vazando
1
@carusocomputing Após uma inspeção mais detalhada, você descobrirá que este não é um diagrama de Venn verdadeiro, porque faltam algumas sobreposições possíveis.
Laikoni

Respostas:

8

Haskell , 71 bytes

Uma função anônima que obtém uma lista de listas de números inteiros e retorna uma lista semelhante.

Use 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))[]

Experimente online!

Como funciona

  • Usa as operações de conjunto \\(diferença) e intersectde Data.List.
  • Dobra a lista de "conjuntos" (representados como listas) em uma lista de células, começando com a lista vazia [].
  • xé o conjunto atual a ser adicionado ao diagrama e ré a lista de células já construídas.
    • x\\(id=<<r)é o subconjunto de elementos xque não estão em nenhuma das células já construídas.
    • [intersect x,(\\x)]<*>rdivide cada célula rconforme seus elementos estejam xou não.
  • Definitivamente, não tenta mesclar células vazias; portanto, existem algumas delas na saída.
Ørjan Johansen
fonte
A mesma ideia da minha implementação, mas dois bytes mais curtos. Bem feito!
Laikoni 8/17/17
4

Geléia , 14 17 bytes

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

Experimente online!

Envio de função (porque o formato que o Jelly imprime nas listas por padrão não faz ida e volta - ele não pode ler seu próprio formato de saída - mas uma função entra e sai no mesmo formato). O link TIO contém um rodapé que executa a função e imprime sua saída no mesmo formato em que a entrada é analisada.

Explicação

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

O requisito de exibir pelo menos um conjunto vazio, se nem todas as seções do diagrama de Venn forem usadas, ocupa mais da metade do programa aqui (é responsável pelo que garante que tenhamos pelo menos um grupo para elementos não correspondentes, o que nos permite para acompanhar quantos conjuntos havia originalmente, mais os últimos nove bytes do código-fonte, exceto o Ġ). A maneira básica pela qual a implementamos é garantir que todos os subconjuntos do diagrama 2 ^ n Venn tenham pelo menos uma entrada, adicionando uma entrada fictícia que preencherá a seção "em nenhum conjunto" e (posteriormente) uma entrada fictícia para cada outra seção, em seguida Ġ, produzirá um grupo para cada subconjunto, que podemos remover usando ṖṖ€.


fonte
Hum, não há restrição para no máximo 7 conjuntos, e um dos casos de teste tem mais.
Ørjan Johansen
Eu assumi que o conjunto original tinha comprimento 3, porque é assim que os diagramas de Venn funcionam, mas aparentemente não? Nesse caso, talvez eu precise de uma maneira diferente de adicionar o conjunto vazio apenas se nem todas as seções do diagrama de Venn estiverem preenchidas. Isso é um defeito no que é uma pergunta bastante elegante.
Bem, você poderia substituir 7 por 2 ^ n-1, presumo.
Ørjan Johansen
Encontrei uma maneira de obter o valor 2 ^ n-1 que corresponde à especificação, mas é dolorosamente longo. Espero que exista um caminho mais curto, mas, mesmo assim, essa pergunta é frustrante.
4

Perl 5, 79 bytes

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

Recebe entrada como uma lista de matrizes anônimas como ([2,3,7], [1,2,4,7,8], [4,7]). Emite um hash em que as chaves são rótulos e os valores são matrizes anônimas correspondentes aos conjuntos de saída.

Como parte de um 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;

Explicação:

Dá a cada conjunto um número inteiro como um rótulo $.,. Cria um hash que armazena um número inteiro para cada elemento exclusivo $_. Adiciona 2**$.para cada conjunto que $_aparece, efetivamente fazendo um mapa binário mostrando em quais conjuntos cada elemento aparece. Finalmente, cria uma matriz anônima para cada célula do diagrama de Venn e empurra os elementos que aparecem nos conjuntos correspondentes para a matriz. Portanto, cada elemento de cada matriz existe nos mesmos conjuntos e, portanto, na mesma célula do diagrama de Venn.

Chris
fonte
3

Pitão , 11 bytes

m-@Fds-Qdty

Suíte de teste.

Como funciona

Cada região do diagrama de Venn representa elementos que estão em [certas combinações dos conjuntos], mas não em [os outros conjuntos].

Portanto, geramos todas as combinações possíveis (e removemos as combinações vazias) localizando o conjunto de potência da entrada.

Para cada combinação gerada, encontramos a interseção dos conjuntos na combinação e filtramos os elementos que estão nos outros 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)
Freira Furada
fonte
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
fonte