Una secuencia gráfica es una secuencia de enteros positivos, cada uno de los cuales denota el número de aristas para un nodo en un gráfico simple . Por ejemplo, la secuencia 2 1 1
denota un gráfico con 3 nodos, uno con 2 aristas y 2 con una conexión.
No todas las secuencias son secuencias gráficas. Por ejemplo, 2 1
no es una secuencia gráfica porque no hay forma de conectar dos nodos para que uno de ellos tenga dos bordes.
Tarea
Tomarás una secuencia de enteros por cualquier método razonable . Esto incluye, entre otros , una matriz de enteros y su tamaño, una lista vinculada de enteros sin signo y un vector de dobles. Puede suponer que no habrá ceros en la entrada. También puede suponer que la entrada se ordena de menor a mayor o de mayor a menor.
Debe mostrar si la secuencia es o no una secuencia gráfica. Un valor verdadero si es un valor falso de lo contrario.
Objetivo
Este es el código de golf, el objetivo es minimizar el número de bytes en su programa
Casos de prueba
Ordenado de mayor a menor
-> True
3 3 3 2 2 2 1 1 1 -> True
3 3 2 2 1 1 -> True
3 3 2 -> False
8 1 1 1 1 1 1 1 1 -> True
1 1 1 1 -> True
1 1 1 -> False
9 5 4 -> False
fuente
0
s para la secuencia vacíaRespuestas:
Mathematica, 25 bytes
Sí, otro incorporado. (Toma la entrada como una lista de enteros positivos). Requiere cargar el
Combinatorica
paquete.fuente
Python 2 (código de salida), 53 bytes
Pruébalo en línea!
Salidas a través del código de salida.
Utiliza una versión del algoritmo Havel-Hakimi. Disminuye repetidamente tanto el elemento más grande
k
como elk
'elemento más grande (sin contarlok
), lo que corresponde a asignar un borde entre los dos vértices con esos grados. Termina con éxito cuando la lista se convierte en todos ceros. De lo contrario, si hay un índice fuera de límites, falla con un error. Cualquier valor negativo creado también eventualmente conduce a un error fuera de los límites.fuente
CJam (20 bytes)
Conjunto de pruebas en línea que incluye un par de pruebas adicionales que agregué para detectar errores en algunos de mis intentos.
Este es un bloque anónimo (función) que toma una matriz de enteros en la pila y se va
0
o1
en la pila. Se supone que la entrada se ordena de forma ascendente.La matriz de entrada puede no estar vacía, pero puede contener ceros, de acuerdo con la respuesta de OP a mi consulta sobre el tema de las entradas vacías.
Disección
Esto sigue la respuesta de OP al implementar el algoritmo Havel-Hakimi .
fuente
Python 2 , 108 bytes
Aquí está mi implementación en Python. Estoy seguro de que puede ser superado por un golfista o matemático más experimentado. Implementa el algoritmo Havel-Hakimi.
Pruébalo en línea!
fuente
[2,1,1]
devuelveTrue
pero[1,1,2]
devuelve0
- EDITAR: acabo de ver que su especificación dice que puede suponer que está ordenada (había visto el caso de prueba9 4 5
).Haskell ,
102 98 9594 bytesPruébalo en línea! Uso:,
f [3,3,2,2,1,1]
devolucionesTrue
oFalse
. Asume que la entradano contiene ceros yestá ordenada en orden descendente, según lo permitido en el desafío.Explicación:
Editar: Esto parece seguir el Havel-Hakimi mencionado en otras respuestas, aunque no conocía este algoritmo al escribir la respuesta.
fuente
length r < x
no es del todo correcto, ya[1,0]
que devolverá verdadero, pero no hay un gráfico simple con 2 nodos con uno y cero bordes.Jalea , 12 bytes
Un enlace monádico que acepta una lista que produce
1
si las respuestas son consistentes de lo contrario0
.Pruébalo en línea! O vea el conjunto de pruebas .
¿Cómo?
fuente
05AB1E ,
2625 bytesPruébalo en línea!
Explicación
fuente
JavaScript (ES6),
82 8076 bytes¡Gracias a ETHproductions por guardar muchos bytes!
Uso
Salida
fuente
map((a,b)=>b<$?a-1:a)
conmap(a=>a-($-->0))
para guardar 4 bytes.R , 20 bytes
¡Mathematica no es el único idioma con funciones integradas! ;-)
El
igraph
paquete necesita ser instalado. Toma la entrada como un vector de enteros.fuente
Rubí , 90 bytes.
Portado de esta pregunta que resultó ser un duplicado de esto. Utiliza Havel-Hakimi ya que ese fue el mencionado en esa pregunta.
Pruébalo en línea!
fuente
05AB1E , 19 bytes
Port of Jonathan : La respuesta de Allan Jelly , ¡así que asegúrate de votarlo!
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
fuente
Stax ,
1412 bytesEjecutar y depurarlo
Este programa maneja entradas vacías y sin clasificar.
fuente