Графическая последовательность представляет собой последовательность положительных целых чисел , обозначающих каждый число ребер для узла в простом графике . Например, последовательность 2 1 1обозначает граф с 3 узлами, один с двумя ребрами и два с одним соединением.

Не все последовательности являются графическими последовательностями. Например, 2 1это не графическая последовательность, потому что нет способа соединить два узла так, чтобы один из них имел два ребра.

задача

Вы возьмете последовательность целых чисел любым разумным способом. Это включает, но не ограничивается , массив целых чисел и его размер, связанный список целых чисел без знака и вектор двойных чисел. Вы можете предположить, что на входе не будет нулей. Вы также можете предположить, что вход сортируется от наименьшего к наибольшему или от наибольшего к наименьшему.

Вы должны вывести, является ли последовательность графической последовательностью. Истинное значение, если в противном случае это ложное значение.

Цель

Это код-гольф, цель которого - минимизировать количество байтов в вашей программе.

Testcases

Отсортировано по величине к минимуму

                  -> 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 байт

<<Combinatorica`
GraphicQ

Да, еще один встроенный. (Принимает входные данные как список натуральных чисел.) Требуется загрузка Combinatoricaпакета.

Python 2 (код выхода), 53 байта

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

Попробуйте онлайн!

Выходы через код выхода.

Использует версию алгоритма Гавела-Хакими. Повторно уменьшает как самый большой элемент, так kи самый kбольшой элемент (не считая kсебя), что соответствует назначению ребра между двумя вершинами с этими степенями. Успешно завершается, когда список становится все нули. В противном случае, если индекс выходит за пределы, происходит ошибка с ошибкой. Любые созданные отрицательные значения также в конечном итоге приводят к ошибке за пределами допустимого диапазона.

CJam (20 байтов)

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

Набор онлайн-тестов, включающий несколько дополнительных тестов, которые я добавил, чтобы ловить ошибки в некоторых из моих попыток.

Это анонимный блок (функция), который принимает массив целых чисел в стеке и оставляет 0или 1в стеке. Предполагается, что вход отсортирован по возрастанию.

Входной массив может быть не пустым, но может содержать нули, в соответствии с ответом OP на мой запрос на предмет пустых входных данных.

рассечение

Это следует за ответом ОП в реализации алгоритма Гавела-Хакими .

{          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 байт

Вот моя реализация в Python. Я уверен, что это может быть побеждено более опытным игроком в гольф или математиком. Он реализует алгоритм Гавела-Хакими.

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

Попробуйте онлайн!

Haskell , 102 98 95 94 байта

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

Попробуйте онлайн! Использование:, f [3,3,2,2,1,1]возвращаетTrue или False. Предполагается, что входные данные не содержат нулей и отсортированы в порядке убывания, как это разрешено в задаче.

Объяснение:

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

Изменить: Это похоже на Havel-Hakimi, упомянутый в других ответах, хотя я не знал об этом алгоритме при написании ответа.

Желе , 12 байт

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

Монадическая ссылка, принимающая список, который выдает, 1если ответы согласуются в противном случае 0.

Попробуйте онлайн! Или посмотрите набор тестов .

Как?

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

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

Попробуйте онлайн!

объяснение

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 байт

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

Спасибо ETHproductions за сохранение большого количества байтов!

использование

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

Выход

1

R , 20 байтов

igraph::is_graphical

Mathematica не единственный язык со встроенными модулями! ;-)

igraphПакет должен быть установлен. Принимает ввод как вектор целых чисел.

Рубин , 90 байт

Портировано из этого вопроса, который оказался дубликатом этого. Использует Гавел-Хакими, поскольку именно этот вопрос упоминается в этом вопросе.

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

Попробуйте онлайн!

05AB1E , 19 байтов

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

Порт JonathanAllan 's Желе ответ , так что обязательно проголосуйте за него !!

Попробуйте онлайн или проверьте все тесты .

Объяснение:

[            # 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 байт

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

Запустите и отладьте его

Эта программа обрабатывает пустые и несортированные входы.