Tarefa

Você receberá um número inteiro positivo e deverá gerar um " gráfico auto-complementar " com muitos nós. Se você não sabe o que é um gráfico auto-complementar, o artigo da wikipedia não o ajudará muito, então abaixo estão duas explicações, uma técnica e uma não técnica.

Não técnico

Um gráfico é um conjunto de nós conectados por linhas. Cada par de pontos pode ser conectado por uma linha ou nenhuma. O "complemento" de um gráfico é o resultado de pegar um gráfico e conectar todos os nós que não estão conectados e desconectar todos os nós que estão.

Um gráfico auto-complementar é um gráfico cujo complemento pode ser reorganizado na forma do original. Abaixo está um exemplo de um gráfico auto-complementar e uma demonstração de como.

Aqui está um gráfico com 5 nós:

Destacaremos todos os lugares em que as conexões podem ir com linhas pontilhadas em vermelho:

Agora vamos encontrar o complemento do gráfico trocando as bordas vermelha e preta:

Isso não se parece com o gráfico original, mas se movermos os nós da seguinte maneira (cada etapa alterna dois nós):

Temos o gráfico original! O gráfico e seu complemento são o mesmo gráfico

Técnico

Um gráfico auto-complementar é um gráfico isomórfico ao seu complemento.

Especificações

Você receberá um número inteiro positivo através do método que melhor lhe convier. E você saída um gráfico em qualquer método que você considerem adequadas, o que inclui, mas não se limita a Matriz de Adjacência Form , Adjacência Lista de Formulários , e, claro, fotografias! O gráfico gerado deve ser seu próprio complemento e ter tantos nós quanto a entrada inteira. Se esse gráfico não existir, você deve gerar um valor falso.

Isso é código-golfe e você deve tentar minimizar sua contagem de bytes.

Casos de teste

Abaixo estão fotos de possíveis saídas para vários n

4

5

9

Haskell , 77 bytes

f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+(last$b:[a|odd n,n==b]))4<2]

Experimente online!

Isso usa um critério explícito fácil de calcular para decidir se uma aresta (a,b)pertence ao gráfico. Instancia esse algoritmo , com a permutação circulando entre os valores do módulo 4

4*m -> 4*m+1 -> 4*m+2 -> 4*m+3 -> 4*m

Incluímos arestas cujos dois vértices do ponto final acrescentam 0 ou 1 módulo 4. Observe que os vértices de ciclismo de acordo com essa permutação adicionam 2 módulos 4 à soma do vértice em cada um e, portanto, trocam arestas e não arestas. Isso permite uma permutação de vértices que complementam as arestas.

Se o gráfico tiver um nó extra além de um múltiplo de 4, ele será colocado em um ciclo sozinho. Incluímos arestas quando outro vértice é par. A permutação dos vértices inverte a paridade e, portanto, o gráfico permanece auto-complementar.

Se o número de vértices não for 0 ou 1 módulo 4, nenhum gráfico auto-complementar é possível porque há um número ímpar de arestas no gráfico completo

No geral, aqui estão as condições:

• Se a entrada n não for 0 ou 1 módulo 4, envie uma lista vazia
• Caso contrário, se n for par, inclua todas as arestas (a,b)com a<be a+biguais a 0 ou 1 módulo 4.
• Caso contrário, se n for ímpar, faça o mesmo, mas inclua as arestas do formulário (a,n)quando a for par.

O código combina o segundo e o terceiro casos, substituindo a condição mod(a+b)4<2por mod(a+a)4<2quando ambos odd ne b==n.

Braquilog 2 , 24 bytes

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧

Experimente online!

Essa é uma função que retorna um par que consiste em duas listas de adjacência: uma para o gráfico e outra para o gráfico de complemento. (No intérprete Brachylog no TIO, você pode pedir para avaliar uma função, em vez de um programa completo, fornecendo Zcomo argumento de linha de comando.) Por exemplo, a saída para entrada 5é:

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

Aqui está o que parece uma imagem (mostrando os dois gráficos):

Como é comum em idiomas baseados em Prolog, a função suporta mais de um padrão de chamada. Notavelmente, se você tentar usá-lo como um gerador, ele produzirá todos os gráficos auto-complementares possíveis com o número determinado de vértices (embora eu não tenha feito nenhum esforço para tornar esse caso utilizável, e, notavelmente, ele produzirá cada um dos os gráficos muitas vezes cada).

Explicação

Isso é basicamente apenas uma descrição do problema, deixando a implementação do Prolog para encontrar o melhor método para resolvê-lo. (No entanto, duvido que ele utilize um algoritmo melhor que a força bruta nesse caso em particular, portanto é provavelmente bastante ineficiente, e os testes parecem confirmar isso, mostrando o desempenho ficando muito pior quanto maior o gráfico.)

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧
 ⟦₁                       The range [1, 2, …, ?], where ? is the input
   ⊇                      A subset of that range…
    Ċ                     …which has exactly two elements
{    }ᶠ                   A list of everything that fits the above description
{⟦₁⊇Ċ}ᶠ                   All edges that could exist in a ?-element graph
       p                  Find a permutation of these…
        ḍ                 …so that splitting it into two equal parts…
          (       ∨   )   …either:
               dl?          produces ? distinct elements
           \                after transposing it
            \ᵐ              and transposing its elements
              c             and flattening one level;
                          or:
                   ?<2      ? was less than 2
         .             ∧  Once you've found it, . specifies what to output

Aliás, acabei tendo que gastar 6 bytes inteiros (¼ do programa, os caracteres (∨?<2)) lidando com os casos especiais de 0 e 1. Frustrante, mas essa é a natureza de casos especiais.

A \\ᵐcdl?seção é um pouco difícil de entender, então aqui está um exemplo. Seu objetivo é verificar se algo é um gráfico e seu complemento, com as arestas correspondentes no gráfico e o complemento na mesma ordem nas listas. O par gráfico / complemento se torna a saída final do programa. Aqui está um exemplo de caso:

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

Transpor isso nos fornece uma lista de pares de arestas correspondentes entre o gráfico e o complemento:

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

Em seguida, transpomos para dentro dos elementos da lista e nivelamos um nível; que nos fornece uma lista de pares de elementos correspondentes entre o gráfico e o complemento:

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

Claramente, o que queremos aqui é que não exista mais de 1 par começando de cada elemento (provando assim que os elementos do gráfico e o complemento estão em correspondência 1 para 1). Quase podemos verificar isso apenas afirmando que a lista possui exatamente ?elementos distintos (ou seja, um número de elementos distintos igual ao número de vértices). Nesse caso, o teste é bem-sucedido; os elementos distintos são:

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

No entanto, isso deixa espaço para um problema em potencial; se um vértice estiver totalmente desconectado no gráfico original, sua correspondência não será mencionada, deixando espaço para uma correspondência duplicada de algum outro vértice. Se este for o caso, o grafo complementar deve ter uma aresta entre esse vértice (sem perda de generalidade, vamos dizer que é 1), e todos os outros vértices, e assim a lista de correspondências conterá [1,2], [1,3], ..., [1, ?]. Quando ?é grande, isso leva a mais correspondências totais do que teríamos de outra forma, portanto não há problema. O único problema ocorre quando ?é 3 ou menos; nesse caso, acabamos adicionando apenas uma correspondência extra (enquanto removemos uma de1não aparece na entrada); no entanto, isso não é um problema na prática, porque existem 3 arestas possíveis em um gráfico de 3 elementos, que é um número ímpar (da mesma forma, 1 aresta possível em um gráfico de 2 elementos também é um número ímpar) e, portanto, o O teste falhará na \etapa (você não pode transpor uma lista irregular, ou seja, aquelas cujos elementos têm comprimentos diferentes).

BBC BASIC, 161 bytes

Tamanho do arquivo tokenizado 140 bytes

Faça o download do intérprete em http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

I.m:IF2ANDm ORm<4P.0:END
r=400n=-2A.m:t=2*PI/n:F.i=1TOn*n:a=i DIVn:b=i MODn:c=b:IFa+b A.2a*=t:b*=t:L.r+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1A.m A.c DRAWr*3,0
N.

Código ungolfed

  INPUTm                           :REM get input
  IF2ANDm ORm<4PRINT0:END          :REM if m=4x+2 or 4x+3 or less than 4, print 0 and exit
  r=400                            :REM radius of diagram
  n=-2ANDm                         :REM n = m truncated to an even number
  t=2*PI/n                         :REM t = 1/n turns
  FORi=1TOn*n                      :REM for each combination of vertices
    a=i DIVn                       :REM extract a and b
    b=i MODn                       :REM make a copy of c
    c=b                            :REM if a+b MOD 4 = 2 or 3, convert a and b to angles and draw edge.
    IFa+b AND2 a*=t:b*=t:LINEr+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1ANDm ANDc DRAWr*3,0
  NEXT                             :REM if m is odd and c is odd, draw a line to the additional vertex for m=4x+1 input.

Explicação

Isso usa o mesmo algoritmo que o Xnor, mas produz uma saída diagramática.

Onde nestá da forma 4x+2ou 4x+3não há solução, pois o número de arestas é ímpar.

Onde né da forma 4x, organizamos todos os vértices em um círculo e desenhamos essas arestas onde (a+b) mod 4é 2 ou 3 (não 0 ou 1, como no caso de Xnor, por razões de golfe. Esse é, portanto, o complemento da solução dada por Xnor.)

Para ver isso em um sentido mais pictórico, pegamos todos os segundos vértices e desenhamos as arestas nos vértices 1 e 2, na direção anti-horária. Isso define ndireções paralelas, metade do total. Em seguida, adicionamos todas as outras arestas paralelas a elas.

O complemento pode ser encontrado adicionando 1 a aeb em cada especificação de aresta ou pictoricamente girando o diagrama uma 1/nvolta.

Onde né da forma 4x + 1, adicionamos outro vértice, que está vinculado a cada segundo vértice do gráfico 4x. Se ele fosse colocado no centro, a simetria do diagrama seria preservada, mas optei por colocá-lo fora do círculo principal de pontos para maior clareza.

Resultado

A seguir, são apresentados os primeiros casos de 4x + 1. os casos 4x podem ser vistos excluindo o vértice no canto inferior direito e as arestas associadas.

JavaScript (ES6), 191 bytes

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

Esta função retorna uma lista de adjacência. Ele usa dois algoritmos e diferencia entre gráficos complementares vazios e não resultados, retornando em 0vez de []quando não existe nenhum. O primeiro algoritmo é baseado nos gráficos do Rado construídos usando o predicado BIT e cria gráficos complementares válidos de 0, 1, 4 e 5 ordens. O outro algoritmo, encontrado por nossos amigos em matemática , constrói um gráfico complementar válido de vértices V + 4 aplicando uma adição de 4 caminhos a um gráfico complementar válido de vértices V.

Ele começa validando a entrada para confirmar a existência de um gráfico complementar válido (usando n*~-n/4%1) e, se isso falhar, retorna 0. Em seguida, ele verifica se n>5e se repete no n-4caso para construir uma solução válida de ordem inferior, e aplica a adição 4 à lista de adjacência retornada no caminho de volta à cadeia de recursão. Por fim, se n>5não for verdadeiro, itera de 0para n-1para xe ye verifica se o valor (y>>x)&1é verdadeiro. Nesse caso, esses nós estão emparelhados.

Aqui está um formato mais legível da função, com operadores ternários expandidos para instruções if-else e eval()s inline:

// precalculate amount of required vertices in v
f = (n, a = [], v = n*~-n / 4) => {
  // if amount is non-integer
  if (v % 1) {
    // no valid complementary graph
    return 0;
  } else {
    if (n > 5) {
      // generate valid (n-4)-order complementary graph
      f(n -= 4, a);
      // apply 4-path addition
      for (i = 0; i < n;)
        a.push([i, n+1],[i++, n+2]);
      a.push([n, ++n], [n, ++n], [n, ++n]);
    } else {
      // construct Rado graph using BIT predicate
      for(l = x = 0; x < n; x++)
        for(y = x; y < n; y++)
          // if amount of pairs is less than required and xth bit of y is high
          if (l < v && (y>>x & 1))
            // vertices x and y should be paired
            a.push([x,y]);
    }
    return a;
  }
};

Demo

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

<input type="number" onchange="o.textContent=JSON.stringify(f(this.value))"><pre id="o"></pre>