Une séquence graphique est une séquence d'entiers positifs indiquant chacun le nombre d'arêtes pour un nœud dans un graphique simple . Par exemple, la séquence 2 1 1indique un graphique à 3 nœuds, un avec 2 arêtes et 2 avec une connexion.

Toutes les séquences ne sont pas des séquences graphiques. Par exemple, ce 2 1n'est pas une séquence graphique car il n'y a aucun moyen de connecter deux nœuds de sorte que l'un d'entre eux ait deux bords.

Tâche

Vous prendrez une séquence d'entiers par toute méthode raisonnable . Cela comprend, mais sans s'y limiter , un tableau d'entiers et sa taille, une liste chaînée d'entiers non signés et un vecteur de doubles. Vous pouvez supposer qu'il n'y aura pas de zéros dans l'entrée. Vous pouvez également supposer que l'entrée est triée du moins au plus grand ou du plus grand au moins.

Vous devez indiquer si la séquence est ou non une séquence graphique. Une valeur vraie si c'est une valeur fausse sinon.

Objectif

Il s'agit de code-golf, l'objectif est de minimiser le nombre d'octets dans votre programme

Cas de test

Trié du plus grand au moins

                  -> 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 octets

<<Combinatorica`
GraphicQ

Ouais, un autre intégré. (Prend l'entrée comme une liste d'entiers positifs.) Nécessite le chargement du Combinatoricapackage.

Python 2 (code de sortie), 53 octets

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

Essayez-le en ligne!

Sorties via code de sortie.

Utilise une version de l'algorithme Havel-Hakimi. Décrémente à la fois le plus grand élément ket le k'e plus grand élément (sans compter klui-même), ce qui correspond à l'attribution d'une arête entre les deux sommets avec ces degrés. Se termine avec succès lorsque la liste devient tous les zéros. Sinon, s'il y a un index hors limites, échoue avec erreur. Toutes les valeurs négatives créées finissent également par conduire à une erreur hors limites.

CJam (20 octets)

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

Suite de tests en ligne comprenant quelques tests supplémentaires que j'ai ajoutés pour détecter des bugs dans certaines de mes tentatives.

Il s'agit d'un bloc (fonction) anonyme qui prend un tableau d'entiers sur la pile et quitte 0ou 1sur la pile. Il suppose que l'entrée est triée en ordre croissant.

Le tableau d'entrée peut ne pas être vide, mais peut contenir des zéros, conformément à la réponse d'OP à ma requête sur le sujet des entrées vides.

Dissection

Cela fait suite à la réponse d'OP dans la mise en œuvre de l' algorithme 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 octets

Voici mon implémentation en Python. Je suis sûr qu'il peut être battu par un golfeur ou un mathématicien plus expérimenté. Il implémente l'algorithme 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]))

Essayez-le en ligne!

Haskell , 102 98 95 94 octets

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

Essayez-le en ligne! Utilisation:, f [3,3,2,2,1,1]retourne Trueou False. Suppose que l'entrée ne contient pas de zéros et est triée par ordre décroissant, comme autorisé dans le défi.

Explication:

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: Cela semble suivre le Havel-Hakimi mentionné dans d'autres réponses, bien que je ne connaissais pas cet algorithme lors de la rédaction de la réponse.

Gelée , 12 octets

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

Un lien monadique acceptant une liste qui donne 1si les réponses sont cohérentes sinon 0.

Essayez-le en ligne! Ou consultez la suite de tests .

Comment?

ṢṚḢ-€+ƊƊƬ>-Ȧ - 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 octets

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

Essayez-le en ligne!

Explication

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 octets

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

Merci à ETHproductions pour avoir économisé de nombreux octets!

Usage

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

Production

1

R , 20 octets

igraph::is_graphical

Mathematica n'est pas le seul langage à intégrer! ;-)

Le igraphpackage doit être installé. Prend l'entrée comme vecteur d'entiers.

Rubis , 90 octets

Porté de cette question qui s'est avérée être un doublon de cela. Utilise Havel-Hakimi puisque c'est celui mentionné dans cette question.

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

Essayez-le en ligne!

05AB1E , 19 octets

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

Port of JonathanAllan 's Jelly answer , alors assurez-vous de lui donner un vote positif !!

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

[            # 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 octets

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

Exécuter et déboguer

Ce programme gère les entrées vides et non triées.