Is this Sequence Graphic?

Question

A graphic sequence is a sequence of positive integers each denoting the number of edges for a node in a simple graph. For example the sequence 2 1 1 denotes a graph with 3 nodes one with 2 edges and 2 with one connection.

Not all sequences are graphic sequences. For example 2 1 is not a graphic sequence because there is no way to connect two nodes so that one of them has two edges.

---

Task

You will take a sequence of integers by any reasonable method. This includes, but is not limited to, an array of integers and its size, a linked list of unsigned integers, and a vector of doubles. You may assume that there will be no zeros in the input. You may also assume the input is sorted from least to greatest or greatest to least.

You must output whether or not the sequence is a graphic sequence. A truthy value if it is a falsy value otherwise.

---

Goal

This is code-golf the goal is to minimize the number of bytes in your program

Testcases

Sorted greatest to least

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

Answer 1

Mathematica, 25 bytes

<<Combinatorica`
GraphicQ

Yeah, another builtin. (Takes the input as a list of positive integers.) Requires loading the Combinatorica package.

Answer 2

Python 2 (exit code), 53 bytes

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

Try it online!

Outputs via exit code.

Uses a version of the Havel-Hakimi algorithm. Repeatedly decrements both the largest element k and the k'th largest element (not counting k itself), which corresponding to assigning an edge between the two vertices with those degrees. Terminates successfully when the list becomes all zeroes. Otherwise, if there's an index out of bounds, fails with error. Any negative values created also eventually lead to an out-of-bounds error.

Answer 3

CJam (20 bytes)

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

Online test suite including a couple of extra tests I added to catch bugs in some of my attempts.

This is an anonymous block (function) which takes an array of integers on the stack and leaves 0 or 1 on the stack. It assumes that the input is sorted ascending.

The input array may not be empty, but may contain zeroes, in accordance with OP's answer to my query on the subject of empty inputs.

Dissection

This follows OP's answer in implementing the Havel-Hakimi algorithm.

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

Answer 4

Python 2, 108 bytes

Here is my implementation in Python. I'm sure it can be beaten by a more experienced golfer or mathematician. It implements the Havel-Hakimi algorithm.

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

Try it online!

Answer 5

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

Try it online! Usage: f [3,3,2,2,1,1], returns True or False. Assumes that the input contains no zeros and is sorted in descending order, as allowed in the challenge.

Explanation:

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: This seems to follow the Havel-Hakimi mentioned in other answers, though I did not know of this algorithm when writing the answer.

Answer 6

Jelly, 12 bytes

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

A monadic Link accepting a list which yields 1 if the answers are consistent otherwise 0.

Try it online! Or see the test-suite.

How?

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

Answer 7

R, 20 bytes

igraph::is_graphical

Mathematica isn't the only language with built-ins! ;-)

The igraph package needs to be installed. Takes input as a vector of integers.

Answer 8

05AB1E, 26 25 bytes

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

Try it online!

Explanation

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

Answer 9

JavaScript (ES6), 82 80 76 bytes

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

Thanks to ETHproductions for saving many bytes!

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

Output

1

Answer 10

Ruby, 90 bytes

Ported from this question which turned out to be a duplicate of this. Uses Havel-Hakimi since that was the one mentioned in that 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}

Try it online!

Answer 11

05AB1E, 19 bytes

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

Port of JonathanAllan's Jelly answer, so make sure to upvote him!!

Try it online or verify all test cases.

Explanation:

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

Answer 12

Stax, 14 12 bytes

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

Run and debug it

This program handles empty and unsorted inputs.