Tarea

Se le dará un número entero positivo y deberá generar un " gráfico autocomplementario " con esa cantidad de nodos. Si no sabe qué es un gráfico autocomplementario, el artículo de wikipedia no lo ayudará mucho, a continuación encontrará dos explicaciones, una técnica y otra no técnica.

No técnico

Un gráfico es un conjunto de nodos que están conectados por líneas. Cada par de puntos se puede conectar por una línea o ninguna. El "complemento" de un gráfico es el resultado de tomar un gráfico y conectar todos los nodos que no están conectados y desconectar todos los nodos que sí lo están.

Un gráfico autocomplementario es un gráfico cuyo complemento se puede reorganizar en la forma del original. A continuación se muestra un ejemplo de un gráfico autocomplementario y una demostración de cómo.

Aquí hay un gráfico con 5 nodos:

Destacaremos todos los lugares donde las conexiones podrían ir con líneas punteadas rojas:

Ahora encontraremos el complemento del gráfico intercambiando los bordes rojo y negro:

Esto no se parece al gráfico original, pero si movemos los nodos de esta manera (cada paso intercambia dos nodos):

¡Obtenemos el gráfico original! El gráfico y su complemento son el mismo gráfico.

Técnico

Un gráfico autocomplementario es un gráfico que es isomorfo a su complemento.

Especificaciones

Recibirá un número entero positivo a través del método que más le convenga. ¡Y generará un gráfico en cualquier método que considere apropiado, esto incluye , entre otros, el formulario de matriz de adyacencia , el formulario de lista de adyacencia y, por supuesto, las imágenes! El gráfico generado debe ser su propio complemento y tener tantos nodos como la entrada entera. Si no existe tal gráfico, debe generar un valor falso.

Este es el código de golf y debe intentar minimizar el recuento de bytes.

Casos de prueba

A continuación se muestran imágenes de posibles salidas para varios n

4 4

5 5

9 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]

Pruébalo en línea!

Esto utiliza un criterio explícito fácil de calcular para decidir si un borde (a,b)pertenece al gráfico. Instancia este algoritmo , con el ciclo de permutación entre los valores del módulo 4

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

Incluimos aristas cuyos dos vértices de punto final se suman a 0 o 1 módulo 4. Tenga en cuenta que los vértices en ciclo según esta permutación agregan 2 módulo 4 a la suma de vértices en cada uno, y así intercambian aristas y no aristas. Esto da una permutación de vértices que complementa los bordes.

Si el gráfico tiene un nodo adicional más allá de un múltiplo de 4, se coloca solo en un ciclo. Incluimos bordes con él cuando el otro vértice es par. Permutar los vértices voltea la paridad, por lo que el gráfico sigue siendo autocomplementario.

Si el número de vértices no es 0 o 1 módulo 4, no es posible un gráfico autocomplementario porque hay un número impar de aristas en el gráfico completo

En general, aquí están las condiciones:

• Si la entrada n no es 0 o 1 módulo 4, genera una lista vacía
• De lo contrario, si n es par, incluya todas las aristas (a,b)con a<be a+bigual a 0 o 1 módulo 4.
• De lo contrario, si n es impar, haga lo mismo, pero incluya bordes del formulario (a,n)cuando a sea par.

El código combina el segundo y el tercer caso al reemplazar la condición mod(a+b)4<2con mod(a+a)4<2cuando ambos odd ny b==n.

Brachylog 2 , 24 bytes

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

Pruébalo en línea!

Esta es una función que devuelve un par que consta de dos listas de adyacencia: una para el gráfico y otra para el gráfico del complemento. (En el intérprete de Brachylog en TIO, puede pedirle que evalúe una función, en lugar de un programa completo, dando Zcomo argumento de línea de comando). Por ejemplo, la salida para la entrada 5es:

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

Así es como se ve como una imagen (que muestra los dos gráficos):

Como es común en los lenguajes basados ​​en Prolog, la función admite más de un patrón de llamada. Notablemente, si intenta usarlo como generador, generará todos los gráficos autocomplementarios posibles con el número dado de vértices (aunque no hice ningún esfuerzo para hacer que este caso sea utilizable, y notablemente generará cada uno de ellos los gráficos muchas veces cada uno).

Explicación

Esto es básicamente una descripción del problema, dejando la implementación de Prolog para encontrar el mejor método para resolverlo. (Sin embargo, dudo que use un algoritmo mejor que la fuerza bruta en este caso particular, por lo que es probable que sea bastante ineficiente, y las pruebas parecen confirmar esto, mostrando que el rendimiento empeora cuanto más grande es el 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

Por cierto, terminé teniendo que gastar un total de 6 bytes (¼ del programa, los caracteres (∨?<2)) tratando con los casos especiales de 0 y 1. Frustrante, pero esa es la naturaleza de los casos especiales.

La \\ᵐcdl?sección es un poco difícil de entender, así que aquí hay un ejemplo trabajado. Su propósito es verificar si algo es un gráfico y su complemento, con los bordes correspondientes en el gráfico y el complemento en el mismo orden dentro de las listas. El par gráfico / complemento se convierte en la salida final del programa. Aquí hay un caso de ejemplo:

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

Transponer esto nos da una lista de pares de aristas correspondientes entre el gráfico y el complemento:

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

A continuación, transponemos dentro de los elementos de la lista y nivelamos un nivel; eso nos da una lista de pares de elementos correspondientes entre el gráfico y el complemento:

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

Claramente, lo que queremos aquí es que no haya más de 1 par a partir de cada elemento (lo que demuestra que los elementos del gráfico y el complemento están en correspondencia 1 a 1). Casi podemos verificar eso simplemente afirmando que la lista tiene ?elementos exactamente distintos (es decir, un número de elementos distintos igual al número de vértices). En este caso, la prueba tiene éxito; Los elementos distintos son:

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

Sin embargo, esto deja espacio para un problema potencial; Si un vértice está completamente desconectado en el gráfico original, no se mencionará su correspondencia, dejando espacio para una correspondencia duplicada de algún otro vértice. Si este es el caso, el gráfico complemento debe tener un borde entre ese vértice (sin pérdida de generalidad, supongamos que es 1), y cada otro vértice, y así la lista de correspondencias contendrá [1,2], [1,3], ..., [1, ?]. Cuando ?es grande, esto conducirá a más correspondencias totales de lo que tendríamos de lo contrario, por lo que no hay problema. El único problema ocurre cuando ?es 3 o menos, en cuyo caso solo terminamos agregando una correspondencia adicional (mientras eliminamos una de1no aparece en la entrada); sin embargo, esto no es un problema en la práctica, porque hay 3 aristas posibles en un gráfico de 3 elementos, que es un número impar (del mismo modo, 1 arista posible en un gráfico de 2 elementos también es un número impar), y por lo tanto el la prueba fallará en el \paso (no puede transponer una lista irregular, es decir, aquellos cuyos elementos tienen longitudes diferentes).

BBC BASIC, 161 bytes

Tamaño de archivo tokenizado 140 bytes

Descargue el intérprete en 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 sin golf

  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.

Explicación

Esto usa el mismo algoritmo que Xnor, pero produce una salida esquemática.

Dónde n es de la forma 4x+2o 4x+3no hay solución ya que el número de aristas es impar.

Dónde n es de la forma 4x, organizamos todos los vértices en un círculo y dibujamos los bordes donde (a+b) mod 4está 2 o 3 (no 0 o 1 como en el caso de Xnor, por razones de golf. Por lo tanto, este es el complemento de la solución dada por Xnor).

Para ver esto en un sentido más pictoral, tomamos cada segundo vértice y dibujamos los bordes hacia los vértices 1 y 2 lugares en sentido antihorario. Esto define ndirecciones paralelas, la mitad del total. Luego agregamos todos los otros bordes paralelos a estos.

El complemento se puede encontrar sumando 1 a a y b en cada especificación de borde, o pictoralmente girando el diagrama por una 1/nvuelta.

Donde nes de la forma 4x + 1 agregamos otro vértice, que está vinculado a cada segundo vértice del gráfico 4x. Si se colocara en el centro, se preservaría la simetría del diagrama, pero decidí colocarlo fuera del círculo principal de puntos para mayor claridad.

Salida

Los siguientes son los primeros casos para 4x + 1. Los casos 4x se pueden ver eliminando el vértice en la parte inferior derecha y sus bordes asociados.

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 función devuelve una lista de adyacencia. Utiliza dos algoritmos y diferencia entre gráficos complementarios vacíos y no salidas al regresar en 0lugar de []cuando no existe ninguno. El primer algoritmo se basa en Gráficos Rado construidos utilizando el predicado BIT , y crea gráficos complementarios válidos de 0, 1, 4 y 5 órdenes. El otro algoritmo, encontrado por nuestros amigos en matemáticas , construye un gráfico complementario de vértice V + 4 válido mediante la aplicación de una adición de 4 rutas a un gráfico complementario de vértice V válido.

Comienza validando la entrada para confirmar la existencia de un gráfico complementario válido (usando n*~-n/4%1), y si eso falla, regresa 0. Luego verifica si n>5y recurre al n-4caso para construir una solución válida de orden inferior, luego aplica la suma 4 a la lista de adyacencia devuelta en el camino de regreso a la cadena de recursión. Por último, si n>5no es cierto, itera a partir 0de n-1para xy y, y comprueba si el (y>>x)&1es cierto. Si es así, esos nodos están emparejados.

Aquí hay un formato más legible de la función, con operadores ternarios expandidos a declaraciones if-else y eval()s en línea:

// 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;
  }
};

Manifestación

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>