Uma sequência gráfica é uma sequência de números inteiros positivos, cada um indicando o número de arestas de um nó em um gráfico simples . Por exemplo, a sequência 2 1 1denota um gráfico com 3 nós, um com 2 arestas e 2 com uma conexão.

Nem todas as sequências são seqüências gráficas. Por exemplo, 2 1não é uma sequência gráfica, porque não há como conectar dois nós para que um deles tenha duas arestas.

Tarefa

Você fará uma sequência de números inteiros por qualquer método razoável . Isso inclui, mas não está limitado a , uma matriz de números inteiros e seu tamanho, uma lista vinculada de números inteiros não assinados e um vetor de dobras. Você pode assumir que não haverá zeros na entrada. Você também pode assumir que a entrada é classificada de menor para maior ou maior para menor.

Você deve mostrar se a sequência é ou não uma sequência gráfica. Um valor verdadeiro, se for um valor falso, caso contrário.

Objetivo

Este é o código-golfe, o objetivo é minimizar o número de bytes no seu programa

Casos de teste

Classificado da melhor para 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

Mathematica, 25 bytes

<<Combinatorica`
GraphicQ

Sim, outro embutido. (Aceita a entrada como uma lista de números inteiros positivos.) Requer o carregamento do Combinatoricapacote.

Python 2 (código de saída), 53 bytes

l=input()
while any(l):l.sort();l[~l[-1]]-=1;l[-1]-=1

Experimente online!

Saídas via código de saída.

Usa uma versão do algoritmo Havel-Hakimi. Diminui repetidamente o elemento maiork e o kdécimo maior elemento (sem contar em ksi), o que corresponde a atribuir uma aresta entre os dois vértices com esses graus. Termina com sucesso quando a lista se torna todos os zeros. Caso contrário, se houver um índice fora dos limites, falha com erro. Quaisquer valores negativos criados também acabam levando a um erro fora dos limites.

CJam (20 bytes)

{{W%(Wa*.+$_0a<!}g!}

Conjunto de testes on-line, incluindo alguns testes extras que adicionei para detectar bugs em algumas de minhas tentativas.

Este é um bloco anônimo (função) que pega uma matriz de números inteiros na pilha e deixa 0 ou 1na pilha. Assume que a entrada é classificada em ordem crescente.

A matriz de entrada pode não estar vazia, mas pode conter zeros, de acordo com a resposta do OP à minha consulta sobre o assunto de entradas vazias.

Dissecação

Isto segue a resposta do OP na implementação do algoritmo Havel-Hakimi .

{          e# Define a block
  {        e#   Do-while loop (which is the reason the array must be non-empty)
           e#     NB At this point the array is assumed to be non-empty and sorted
    W%     e#     Reverse
    (Wa*.+ e#     Pop the first element and subtract 1 from that many subsequent
           e#     elements. If there aren't enough, it adds -1s to the end. That's
           e#     the reason for using W (i.e. -1) and .+ instead of 1 and .-
    $      e#     Sort, restoring that part of the invariant
    _0a<!  e#     Continue looping if array >= [0]
           e#     Equivalently, break out of the loop if it starts with a negative
           e#     number or is empty
  }g
  !        e#   Logical not, so that an empty array becomes truthy and an array
           e#   with a negative number becomes falsy
}

Python 2 , 108 bytes

Aqui está minha implementação em Python. Tenho certeza de que pode ser derrotado por um golfista ou matemático mais experiente. Ele implementa o algoritmo Havel-Hakimi.

def f(x):p=x[0]+1;x=sorted(x+[0]*p)[::-1];return~x[-1]and(p<2or f(sorted([a-1for a in x[1:p]]+x[p:])[::-1]))

Experimente online!

Haskell , 102 98 95 94 bytes

import Data.List
f(x:r)=length r>=x&&x>=0&&(f.reverse.sort$take x(pred<$>r)++drop x r)
f x=1<3

Experimente online! Uso:, f [3,3,2,2,1,1]retornos Trueou False. Assume que a entrada não contém zeros e é classificada em ordem decrescente, conforme permitido no desafio.

Explicação:

import Data.List          -- import needed for sort
f (x:r) =                 -- x is the first list element, r the rest list
  length r >= x           -- the rest list r must be longer or equal x
  && x >= 0               -- and x must not be negative
  && (f .                 -- and the recursive call of f
      reverse . sort $    --    with the descendingly sorted list
      take x(pred<$>r)    --    of the first x elements of r subtracted by 1
      ++ drop x r         --    and the rest of r
     )                    -- must be true
f [] = True               -- if the list is empty, return True

Edit: Isso parece seguir o Havel-Hakimi mencionado em outras respostas, embora eu não conhecesse esse algoritmo ao escrever a resposta.

Gelatina , 12 bytes

ṢṚḢ-€+ƊƊƬ>-Ȧ

Um link monádico que aceita uma lista que gera 1se as respostas forem consistentes de outra forma 0.

Experimente online! Ou veja a suíte de testes .

Quão?

ṢṚḢ-€+ƊƊƬ>-Ȧ - Link: list of integers
        Ƭ    - collect up while results change:
       Ɗ     -   last three links as a monad i.e. f(L):
Ṣ            -     sort                      [min(L),...,max(L)]
 Ṛ           -     reverse                   [max(L),...,min(L)]
      Ɗ      -     last three links as a monad i.e. f([a,b,c,...,x]):
  Ḣ          -       pop head                          a
   -€        -       -1 for each                       [-1,-1,...,-1] (length a)
     +       -       add to head result (vectorises)   [b-1,c-1,...,x-1,-1,-1,...]
         >-  - greater than -1? (vectorises)
           Ȧ - Any and all? (0 if empty or contains a 0 when flattened, else 1)

05AB1E , 26 25 bytes

D0*«¹v{R¬U¦X¹gn‚£`s<ì}0QP

Experimente online!

Explicação

D0*«                       # extend the input list with as many zeroes as it has elements
    ¹v                     # len(input) times do:
      {R                   # sort in descending order
        ¬U¦X               # extract the first element of the list
            ¹gn‚           # pair it with len(input)^2
                £          # partition the list in 2 parts, the first the size of the 
                           # extracted element, the second containing the rest of the list
                 `         # split these list to stack (the second on top)
                  s<       # decrement the elements of the first list by 1
                    ì      # prepend it to the rest of the list
                     }     # end loop
                      0Q   # compare each element in the resulting list with 0
                        P  # reduce list by multiplication

JavaScript (ES6), 82 80 76 bytes

f=([$,..._])=>1/$?_.length>=$&$>=0&f(_.map(a=>a-($-->0)).sort((a,b)=>b-a)):1

Obrigado a ETHproductions por economizar muitos bytes!

Uso

f=([$,..._])=>1/$?_.length>=$&$>=0&f(_.map(a=>a-($-->0)).sort((a,b)=>b-a)):1
f([3,3,3,2,2,2,1,1,1])

Resultado

1

R , 20 bytes

igraph::is_graphical

O Mathematica não é o único idioma com built-ins! ;-)

O igraphpacote precisa ser instalado. Recebe entrada como um vetor de números inteiros.

Ruby , 90 bytes

Portado desta pergunta que acabou sendo uma duplicata disso. Usa Havel-Hakimi, já que foi o mencionado nessa pergunta.

->a{b=1;(a.sort_by!(&:-@);i=a.shift;a.map!{|e|i>0&&e>0?(i-=1;e-1):e};b&&=i<1)while[]!=a;b}

Experimente online!

05AB1E , 19 bytes

[D{RćD1‹#Å0<0ζO})dW

Resposta da geléia do porto de JonathanAllan , por isso não deixe de vota-lo!

Experimente online ou verifique todos os casos de teste .

Explicação:

[            # Start an infinite loop:
 D           #  Duplicate the current list
             #  (which is the implicit input-list in the first iteration)
  {R         #  Sort it from highest to lowest
    ć        #  Extract the head; pop and push the remainder and head
     D1‹     #  If the head is 0 or negative:
        #    #   Stop the infinite loop
     Å0<     #  Create a list of the head amount of -1
        0ζ   #  Zip/transpose it with the remainder list, with 0 as filler
          O  #  Sum each pair
})           # After the loop: wrap everything on the stack into a list
  d          # Check for each value if it's non-negative (>= 0)
             # (resulting in 1/0 for truthy/falsey respectively)
   W         # Get the flattened minimum (so basically check if none are falsey)
             # (which is output implicitly as result)

Stax , 14 12 bytes

ε▼ü*æε<%)4‼♂

Execute e depure

Este programa lida com entradas vazias e não classificadas.