Graficzny sekwencja jest sekwencją dodatnich liczb całkowitych każdego oznaczającą liczbę krawędzi dla węzła w prosty wykres . Na przykład sekwencja2 1 1 oznacza wykres z 3 węzłami, jeden z 2 krawędziami i 2 z jednym połączeniem.

Nie wszystkie sekwencje są sekwencjami graficznymi. Na przykład 2 1nie jest sekwencją graficzną, ponieważ nie ma sposobu połączenia dwóch węzłów, aby jeden z nich miał dwie krawędzie.

Zadanie

Weźmiesz ciąg liczb całkowitych dowolną rozsądną metodą. Obejmuje to między innymi tablicę liczb całkowitych i jej rozmiar, połączoną listę liczb całkowitych bez znaku oraz wektor podwójnych. Możesz założyć, że na wejściu nie będzie zer. Możesz również założyć, że dane wejściowe są posortowane od najmniejszej do największej lub od największej do najmniejszej.

Musisz podać, czy sekwencja jest sekwencją graficzną. Prawdziwa wartość, jeśli w przeciwnym razie jest to wartość fałszywa.

Cel

To jest golf golfowy, którego celem jest zminimalizowanie liczby bajtów w twoim programie

Przypadki testowe

Posortowane od największego do najmniejszego

                  -> 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 bajtów

<<Combinatorica`
GraphicQ

Tak, kolejne wbudowane. (Traktuje dane wejściowe jako listę liczb całkowitych dodatnich.) Wymaga załadowania Combinatoricapakietu.

Python 2 (kod wyjścia), 53 bajty

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

Wypróbuj online!

Dane wyjściowe za pośrednictwem kodu wyjścia.

Wykorzystuje wersję algorytmu Havel-Hakimi. Wielokrotnie zmniejsza zarówno największy element, jak ki knajwiększy element (nie licząc księ), co odpowiada przypisaniu krawędzi między dwoma wierzchołkami o tych stopniach. Kończy się pomyślnie, gdy lista staje się zerami. W przeciwnym razie, jeśli indeks jest poza zakresem, błąd kończy się niepowodzeniem. Wszelkie utworzone wartości ujemne również ostatecznie prowadzą do błędu przekroczenia granicy.

CJam (20 bajtów)

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

Zestaw testów online zawierający kilka dodatkowych testów, które dodałem, aby wykryć błędy w niektórych moich próbach.

Jest to anonimowy blok (funkcja), który pobiera tablicę liczb całkowitych na stos i opuszcza 0lub 1na stos. Zakłada się, że dane wejściowe są sortowane rosnąco.

Tablica wejściowa może nie być pusta, ale może zawierać zera, zgodnie z odpowiedzią OP na moje zapytanie na temat pustych danych wejściowych.

Sekcja

Jest to zgodne z odpowiedzią OP na wdrożenie algorytmu 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 bajtów

Oto moja implementacja w Pythonie. Jestem pewien, że może go pokonać bardziej doświadczony golfista lub matematyk. Implementuje algorytm Havela-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]))

Wypróbuj online!

Haskell , 102 98 95 94 bajtów

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

Wypróbuj online! Zastosowanie: f [3,3,2,2,1,1]zwraca Truelub False. Zakłada, że ​​dane wejściowe nie zawierają zer i są sortowane w kolejności malejącej, jak dozwolone w wyzwaniu.

Wyjaśnienie:

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

Edycja: Wydaje się, że jest to zgodne z Havel-Hakimi wspomnianym w innych odpowiedziach, chociaż nie znałem tego algorytmu podczas pisania odpowiedzi.

Galaretka , 12 bajtów

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

Monadyczny link akceptujący listę, która daje wynik, 1jeśli odpowiedzi są spójne inaczej 0.

Wypróbuj online!Lub zobacz zestaw testowy .

W jaki sposób?

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

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

Wypróbuj online!

Wyjaśnienie

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 bajtów

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

Dzięki produktom ETH za oszczędność wielu bajtów!

Stosowanie

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

Wynik

1

R , 20 bajtów

igraph::is_graphical

Mathematica nie jest jedynym językiem z wbudowanymi funkcjami! ;-)

igraphPakiet musi być zainstalowany. Pobiera dane wejściowe jako wektor liczb całkowitych.

Rubin , 90 bajtów

Przeniesione z tego pytania, które okazało się duplikatem tego. Używa Havela-Hakimi, ponieważ był to ten, o którym wspomniano w tym pytaniu.

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

Wypróbuj online!

05AB1E , 19 bajtów

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

Port z JonathanAllan 's Jelly odpowiedź , więc upewnij się, że go głosujesz !!

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

[            # 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 bajtów

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

Uruchom i debuguj

Ten program obsługuje puste i nieposortowane dane wejściowe.