Sebuah urutan grafis adalah urutan bilangan bulat positif setiap yang menunjukkan jumlah tepi untuk node dalam grafik sederhana . Misalnya urutan 2 1 1menunjukkan grafik dengan 3 node satu dengan 2 tepi dan 2 dengan satu koneksi.

Tidak semua urutan adalah urutan grafik. Misalnya 2 1bukan urutan grafis karena tidak ada cara untuk menghubungkan dua node sehingga salah satu dari mereka memiliki dua sisi.

Tugas

Anda akan mengambil urutan bilangan bulat dengan metode apa pun yang masuk akal . Ini termasuk, tetapi tidak terbatas pada , array bilangan bulat dan ukurannya, daftar tertaut bilangan bulat yang tidak ditandatangani, dan vektor ganda. Anda dapat berasumsi bahwa tidak akan ada nol pada input. Anda juga dapat berasumsi bahwa input diurutkan dari paling tidak ke terhebat atau terhebat ke yang terkecil.

Anda harus menampilkan apakah urutannya adalah urutan grafik atau tidak. Nilai sebenarnya jika itu nilai salah jika tidak.

Tujuan

Ini adalah kode-golf tujuannya adalah untuk meminimalkan jumlah byte dalam program Anda

Testcases

Diurutkan terbesar ke paling tidak

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

<<Combinatorica`
GraphicQ

Ya, builtin lain. (Mengambil input sebagai daftar bilangan bulat positif.) Membutuhkan pemuatan Combinatoricapaket.

Python 2 (kode keluar), 53 byte

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

Cobalah online!

Keluaran melalui kode keluar.

Menggunakan versi algoritma Havel-Hakimi. Berkali-kali mengurangi elemen terbesar kdan elemen terbesar kke-10 (tidak termasuk kdirinya sendiri), yang sesuai untuk menetapkan batas antara dua simpul dengan derajat tersebut. Berakhir dengan sukses ketika daftar menjadi nol semua. Kalau tidak, jika ada indeks di luar batas, gagal dengan kesalahan. Nilai negatif apa pun yang dibuat juga pada akhirnya menyebabkan kesalahan di luar batas.

CJam (20 byte)

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

Test suite online termasuk beberapa tes tambahan yang saya tambahkan untuk menangkap bug dalam beberapa upaya saya.

Ini adalah blok anonim (fungsi) yang mengambil array bilangan bulat di tumpukan dan daun 0atau 1di tumpukan. Diasumsikan bahwa input diurutkan naik.

Array input mungkin tidak kosong, tetapi mungkin mengandung angka nol, sesuai dengan jawaban OP atas permintaan saya tentang masalah input kosong.

Pembedahan

Ini mengikuti jawaban OP dalam mengimplementasikan algoritma 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 byte

Ini implementasi saya dengan Python. Saya yakin itu bisa dikalahkan oleh pegolf atau ahli matematika yang lebih berpengalaman. Ini mengimplementasikan algoritma 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]))

Cobalah online!

Haskell , 102 98 95 94 byte

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

Cobalah online! Penggunaan:, f [3,3,2,2,1,1]mengembalikan Trueatau False. Mengasumsikan bahwa input tidak mengandung nol dan diurutkan dalam urutan menurun, sebagaimana diizinkan dalam tantangan.

Penjelasan:

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

Sunting: Ini sepertinya mengikuti Havel-Hakimi yang disebutkan dalam jawaban lain, meskipun saya tidak tahu algoritma ini ketika menulis jawabannya.

Jelly , 12 byte

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

Tautan monadik yang menerima daftar yang menghasilkan 1 jika jawabannya konsisten sebaliknya 0.

Cobalah online! Atau lihat test-suite .

Bagaimana?

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

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

Cobalah online!

Penjelasan

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 byte

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

Terima kasih untuk produk ETH karena telah menghemat banyak byte!

Pemakaian

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

Keluaran

1

R , 20 byte

igraph::is_graphical

Mathematica bukan satu-satunya bahasa dengan built-in! ;-)

The igraphpaket harus diinstal. Mengambil input sebagai vektor bilangan bulat.

Ruby , 90 byte

Diterjemahkan dari pertanyaan ini yang ternyata merupakan duplikat dari ini. Menggunakan Havel-Hakimi karena itulah yang disebutkan dalam pertanyaan itu.

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

Cobalah online!

05AB1E , 19 byte

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

Port of Jonathan Allan menjawab Jelly , jadi pastikan untuk membesarkan hatinya !!

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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

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

Jalankan dan debug itu

Program ini menangani input yang kosong dan tidak disortir.