Eine Grafiksequenz ist eine Folge von positiven ganzen Zahlen, die jeweils die Anzahl der Kanten für einen Knoten in einem einfachen Diagramm angeben . Zum Beispiel bezeichnet die Sequenz 2 1 1einen Graphen mit 3 Knoten, einer mit 2 Kanten und zwei mit einer Verbindung.

Nicht alle Sequenzen sind grafische Sequenzen. Beispielsweise 2 1handelt es sich nicht um eine grafische Sequenz, da es keine Möglichkeit gibt, zwei Knoten so zu verbinden, dass einer von ihnen zwei Kanten hat.

Aufgabe

Sie werden eine Folge von ganzen Zahlen nach jeder vernünftigen Methode nehmen. Dies umfasst, ohne darauf beschränkt zu sein , ein Array von Ganzzahlen und deren Größe, eine verknüpfte Liste von Ganzzahlen ohne Vorzeichen und einen Vektor von Doppelwerten. Sie können davon ausgehen, dass die Eingabe keine Nullen enthält. Sie können auch davon ausgehen, dass die Eingabe vom kleinsten zum größten oder vom größten zum kleinsten sortiert ist.

Sie müssen ausgeben, ob die Sequenz eine grafische Sequenz ist oder nicht. Ein wahrer Wert, wenn es sich sonst um einen falschen Wert handelt.

Tor

Dies ist Code-Golf. Ziel ist es, die Anzahl der Bytes in Ihrem Programm zu minimieren

Testfälle

Vom größten zum kleinsten sortiert

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

Ja, noch ein eingebautes. (Nimmt die Eingabe als Liste positiver Ganzzahlen.) Erfordert das Laden des CombinatoricaPakets.

Python 2 (Exit-Code), 53 Byte

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

Probieren Sie es online!

Ausgänge über Exit-Code.

Verwendet eine Version des Havel-Hakimi-Algorithmus. Verringert wiederholt sowohl das größte Element kals auch das k'größte Element (zählt nicht kselbst), was dem Zuweisen einer Kante zwischen den beiden Scheitelpunkten mit diesen Graden entspricht. Wird erfolgreich beendet, wenn die Liste alle Nullen enthält. Andernfalls schlägt ein Fehler fehl, wenn ein Index außerhalb der Grenzen liegt. Alle negativen Werte, die erstellt werden, führen schließlich auch zu einem Fehler außerhalb der Grenzen.

CJam (20 Bytes)

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

Online-Testsuite mit einigen zusätzlichen Tests, die ich hinzugefügt habe, um Fehler bei einigen meiner Versuche zu erkennen.

Dies ist ein anonymer Block (eine Funktion), der ein Array von Ganzzahlen auf dem Stapel nimmt und 0oder 1auf dem Stapel verlässt . Es wird davon ausgegangen, dass die Eingabe aufsteigend sortiert ist.

Das Eingabearray darf nicht leer sein, sondern darf gemäß der Antwort von OP auf meine Anfrage zum Thema Leereingaben Nullen enthalten.

Präparation

Dies folgt der Antwort von OP bei der Implementierung des Havel-Hakimi-Algorithmus .

{          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

Hier ist meine Implementierung in Python. Ich bin sicher, es kann von einem erfahrenen Golfer oder Mathematiker geschlagen werden. Es implementiert den Havel-Hakimi-Algorithmus.

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

Probieren Sie es 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

Probieren Sie es online! Verwendung:, f [3,3,2,2,1,1]gibt Trueoder zurück False. Es wird davon ausgegangen, dass die Eingabe keine Nullen enthält und in absteigender Reihenfolge sortiert ist, wie dies in der Abfrage zulässig ist.

Erläuterung:

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: Dies scheint dem in anderen Antworten erwähnten Havel-Hakimi zu folgen, obwohl ich diesen Algorithmus beim Schreiben der Antwort nicht kannte.

Gelee , 12 Bytes

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

Ein monadischer Link, der eine Liste akzeptiert, die ergibt, 1wenn die Antworten ansonsten konsistent sind 0.

Probieren Sie es online! Oder sehen Sie sich die Testsuite an .

Wie?

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

Probieren Sie es online!

Erläuterung

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

Vielen Dank an ETHproductions für die Einsparung von vielen Bytes!

Verwendung

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

Ausgabe

1

R , 20 Bytes

igraph::is_graphical

Mathematica ist nicht die einzige Sprache mit integrierten Funktionen! ;-)

Das igraphPaket muss installiert sein. Nimmt die Eingabe als Vektor von ganzen Zahlen.

Rubin , 90 Bytes

Portiert von dieser Frage, die sich als ein Duplikat davon herausstellte. Verwendet Havel-Hakimi, da dies in dieser Frage erwähnt wurde.

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

Probieren Sie es online!

05AB1E , 19 Bytes

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

Port of JonathanAllans Gelee-Antwort , also stelle sicher, dass du ihn positiv bewertest !!

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

[            # 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‼♂

Führen Sie es aus und debuggen Sie es

Dieses Programm verarbeitet leere und unsortierte Eingaben.