Tugas

Anda akan diberi bilangan bulat positif dan Anda harus menampilkan " grafik pelengkap diri " dengan banyak node. Jika Anda tidak tahu apa itu grafik pelengkap diri adalah artikel wikipedia tidak akan banyak membantu Anda jadi di bawah ini adalah dua penjelasan, satu teknis dan non-teknis.

Non-Teknis

Grafik adalah sekumpulan node yang dihubungkan oleh garis. Setiap pasangan poin dapat dihubungkan oleh satu garis atau tidak sama sekali. "Komplemen" dari grafik adalah hasil dari mengambil grafik dan menghubungkan semua node yang tidak terhubung dan memutuskan semua node yang ada.

Grafik pelengkap diri adalah grafik yang komplemennya dapat disusun ulang menjadi bentuk aslinya. Di bawah ini adalah contoh dari grafik pelengkap diri dan demonstrasi bagaimana.

Berikut ini adalah grafik dengan 5 node:

Kami akan menyoroti semua tempat koneksi dapat dilakukan dengan garis putus-putus merah:

Sekarang kita akan menemukan komplemen grafik dengan menukar tepi merah dan hitam:

Ini tidak terlihat seperti grafik asli tetapi jika kita memindahkan node seperti itu (setiap langkah menukar dua node):

Kami mendapatkan grafik asli! Grafik dan komplemennya adalah grafik yang sama

Teknis

Grafik pelengkap diri adalah grafik yang isomorfis untuk pelengkapnya.

Spesifikasi

Anda akan menerima bilangan bulat positif melalui metode apa pun yang paling sesuai untuk Anda. Dan Anda akan menampilkan grafik dalam metode apa pun yang Anda anggap tepat, ini termasuk tetapi tidak terbatas pada kedekatan Matrix Form , kedekatan Daftar Form , dan tentu saja gambar! Grafik yang dihasilkan haruslah komplemennya sendiri dan memiliki simpul sebanyak input integer. Jika tidak ada grafik seperti itu, Anda harus menampilkan nilai falsy.

Ini adalah kode-golf dan Anda harus berusaha meminimalkan jumlah byte Anda.

Uji Kasus

Di bawah ini adalah gambar-gambar dari kemungkinan keluaran untuk beberapa n

4

5

9

Haskell , 77 byte

f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+(last$b:[a|odd n,n==b]))4<2]

Cobalah online!

Ini menggunakan kriteria eksplisit yang mudah dihitung untuk memutuskan apakah suatu edge (a,b)termasuk dalam grafik. Instantiates algoritma ini , dengan permutasi siklus antara nilai-nilai modulo 4

4*m -> 4*m+1 -> 4*m+2 -> 4*m+3 -> 4*m

Kami menyertakan tepi yang dua simpul titik akhirnya menambah 0 atau 1 modulo 4. Perhatikan bahwa simpul bersepeda sesuai permutasi ini menambahkan 2 modulo 4 ke jumlah simpul pada masing-masing, dan juga menukar tepi dan non-tepi. Ini memberikan permutasi simpul yang melengkapi tepi.

Jika grafik memiliki simpul tambahan di luar kelipatan 4, grafik itu diletakkan dalam satu siklus saja. Kami menyertakan tepi dengan itu ketika kemudian titik lainnya genap. Mengganti simpul membalik paritas, dan grafik tetap saling melengkapi.

Jika jumlah simpul bukan 0 atau 1 modulo 4, tidak mungkin ada grafik pelengkap diri karena ada jumlah tepi yang ganjil dalam grafik lengkap

Secara keseluruhan, berikut ini kondisinya:

• Jika input n bukan 0 atau 1 modulo 4, keluarkan daftar kosong
• Kalau tidak, jika n genap, sertakan semua sisi (a,b)dengan a<bdan a+bsama dengan 0 atau 1 modulo 4.
• Kalau tidak, jika n ganjil, lakukan hal yang sama, tetapi sebaliknya sertakan ujung-ujung bentuk (a,n)ketika a adalah genap.

Kode menggabungkan kasus kedua dan ketiga dengan mengganti kondisi mod(a+b)4<2dengan mod(a+a)4<2saat keduanya odd ndan b==n.

Brachylog 2 , 24 byte

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧

Cobalah online!

Ini adalah fungsi yang mengembalikan pasangan yang terdiri dari dua daftar adjacency: satu untuk grafik, satu untuk grafik komplemen. (Dalam penerjemah Brachylog pada TIO, Anda dapat memintanya untuk mengevaluasi suatu fungsi, bukan program lengkap, melalui pemberian Zsebagai argumen baris perintah.) Misalnya, output untuk input 5adalah:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Inilah yang terlihat seperti gambar (menampilkan dua grafik):

Seperti biasa dalam bahasa berbasis Prolog, fungsi ini mendukung lebih dari satu pola panggilan. Khususnya, jika Anda mencoba menggunakannya sebagai generator, itu akan menampilkan semua kemungkinan grafik pelengkap diri dengan jumlah simpul yang diberikan (meskipun saya tidak melakukan upaya apa pun untuk membuat case ini dapat digunakan, dan terutama itu akan menampilkan masing-masing masing-masing grafik berkali-kali).

Penjelasan

Ini pada dasarnya hanya deskripsi masalah, meninggalkan implementasi Prolog untuk menemukan metode terbaik untuk menyelesaikannya. (Namun, saya ragu itu akan menggunakan algoritma yang lebih baik daripada brute force dalam kasus khusus ini, jadi sepertinya cukup tidak efisien, dan pengujian tampaknya mengkonfirmasi hal ini, menunjukkan kinerja yang semakin buruk semakin besar grafiknya.)

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧
 ⟦₁                       The range [1, 2, …, ?], where ? is the input
   ⊇                      A subset of that range…
    Ċ                     …which has exactly two elements
{    }ᶠ                   A list of everything that fits the above description
{⟦₁⊇Ċ}ᶠ                   All edges that could exist in a ?-element graph
       p                  Find a permutation of these…
        ḍ                 …so that splitting it into two equal parts…
          (       ∨   )   …either:
               dl?          produces ? distinct elements
           \                after transposing it
            \ᵐ              and transposing its elements
              c             and flattening one level;
                          or:
                   ?<2      ? was less than 2
         .             ∧  Once you've found it, . specifies what to output

Kebetulan, saya akhirnya harus menghabiskan seluruh 6 byte (¼ dari program, karakter (∨?<2)) berurusan dengan kasus-kasus khusus 0 dan 1. Frustasi, tetapi itulah sifat kasus khusus.

The \\ᵐcdl?Bagian agak sulit untuk memahami, jadi di sini adalah contoh dikerjakan. Tujuannya adalah untuk memeriksa apakah sesuatu adalah grafik dan komplemennya, dengan tepi yang sesuai dalam grafik dan komplemen berada dalam urutan yang sama dalam daftar. Pasangan grafik / pelengkap menjadi hasil akhir dari program. Berikut ini contoh kasusnya:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Transposing ini memberi kita daftar pasangan tepi yang sesuai antara grafik dan komplemen:

[[[1,2],[2,5]],[[1,3],[2,3]],[[1,5],[2,4]],[[3,5],[3,4]],[[4,5],[1,4]]

Selanjutnya, kita transpos di dalam elemen daftar dan ratakan satu tingkat; yang memberi kita daftar pasangan elemen yang sesuai antara grafik dan komplemen:

[[1,2],[2,5],[1,2],[3,3],[1,2],[5,4],[3,3],[5,4],[4,1],[5,4]]

Jelas, apa yang kita inginkan di sini adalah agar tidak ada lebih dari 1 pasangan yang dimulai dari setiap elemen (dengan demikian membuktikan bahwa elemen-elemen dari grafik dan komplemen ada dalam korespondensi 1-ke-1). Kita hampir dapat memverifikasi bahwa hanya dengan menyatakan bahwa daftar memiliki ?elemen yang persis berbeda (yaitu sejumlah elemen berbeda sama dengan jumlah simpul). Dalam hal ini, tes berhasil; elemen yang berbeda adalah:

[[1,2],[2,5],[3,3],[5,4],[4,1]]

Namun, ini menyisakan ruang untuk masalah potensial; jika sebuah simpul sepenuhnya terputus dalam grafik asli, korespondensinya tidak akan disebutkan, menyisakan ruang untuk korespondensi duplikat dari beberapa simpul lainnya. Jika hal ini terjadi, grafik pelengkap harus memiliki keunggulan antara titik yang (tanpa kehilangan umum, katakanlah itu 1), dan setiap vertex lainnya, sehingga daftar korespondensi akan berisi [1,2], [1,3], ..., [1, ?]. Ketika ?besar, ini akan menyebabkan total korespondensi lebih dari yang kita miliki, jadi tidak ada masalah. Satu-satunya masalah terjadi ketika ?3 atau lebih rendah, dalam hal ini kami hanya menambahkan satu korespondensi tambahan (sambil menghapus satu dari1tidak muncul di input); Namun, ini bukan masalah dalam praktiknya, karena ada 3 kemungkinan tepi pada grafik 3-elemen, yang merupakan angka ganjil (demikian juga, 1 tepi yang mungkin pada grafik 2-elemen juga merupakan angka ganjil), dan dengan demikian tes akan gagal pada \langkah (Anda tidak dapat mengubah daftar yang kasar, yaitu orang-orang yang elemen-elemennya memiliki panjang yang berbeda).

BBC BASIC, 161 byte

File Tokenised berukuran 140 byte

Unduh juru bahasa di http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

I.m:IF2ANDm ORm<4P.0:END
r=400n=-2A.m:t=2*PI/n:F.i=1TOn*n:a=i DIVn:b=i MODn:c=b:IFa+b A.2a*=t:b*=t:L.r+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1A.m A.c DRAWr*3,0
N.

Kode tidak dikunci

  INPUTm                           :REM get input
  IF2ANDm ORm<4PRINT0:END          :REM if m=4x+2 or 4x+3 or less than 4, print 0 and exit
  r=400                            :REM radius of diagram
  n=-2ANDm                         :REM n = m truncated to an even number
  t=2*PI/n                         :REM t = 1/n turns
  FORi=1TOn*n                      :REM for each combination of vertices
    a=i DIVn                       :REM extract a and b
    b=i MODn                       :REM make a copy of c
    c=b                            :REM if a+b MOD 4 = 2 or 3, convert a and b to angles and draw edge.
    IFa+b AND2 a*=t:b*=t:LINEr+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1ANDm ANDc DRAWr*3,0
  NEXT                             :REM if m is odd and c is odd, draw a line to the additional vertex for m=4x+1 input.

Penjelasan

Ini menggunakan algoritma yang sama dengan Xnor, tetapi menghasilkan output diagram.

Di mana nbentuk 4x+2atau 4x+3tidak ada solusi karena jumlah tepi aneh.

Di mana ndari bentuk 4x kami mengatur semua simpul dalam lingkaran dan menggambar ujung-ujungnya di mana (a+b) mod 42 atau 3 (bukan 0 atau 1 seperti dalam kasus Xnor, karena alasan bermain golf. Oleh karena itu, ini adalah pelengkap dari solusi yang diberikan oleh Xnor.)

Untuk melihatnya dalam pengertian yang lebih piktural, kami mengambil setiap titik kedua dan menarik ujung-ujungnya ke titik 1 dan 2 ke arah yang berlawanan arah jarum jam. Ini mendefinisikan narah paralel, setengah dari total. Kemudian kami menambahkan semua tepi lainnya sejajar dengan ini.

Komplemen dapat ditemukan dengan menambahkan 1 ke a dan b di setiap spesifikasi tepi, atau secara gambar dengan memutar diagram dengan 1/nbelokan.

Di mana ndari bentuk 4x + 1 kita menambahkan simpul lain, yang terhubung ke setiap simpul kedua dari grafik 4x. Jika ditempatkan di tengah, simetri diagram akan dipertahankan, tetapi saya memilih untuk meletakkannya di luar lingkaran utama poin untuk kejelasan.

Keluaran

Berikut ini adalah beberapa kasus pertama untuk 4x + 1. kasing 4x dapat dilihat dengan menghapus titik di kanan bawah dan tepi yang terkait.

JavaScript (ES6), 191 byte

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

Fungsi ini mengembalikan daftar adjacency. Ini menggunakan dua algoritma, dan membedakan antara grafik komplementer kosong dan non-output dengan mengembalikan 0bukan []ketika tidak ada. Algoritme pertama didasarkan pada Grafik Rado yang dibangun menggunakan predikat BIT , dan menciptakan grafik komplementer yang sesuai dengan urutan 0, 1-, 4-, dan 5. Algoritme lain, yang ditemukan oleh teman-teman kami di matematika , membuat grafik pelengkap verteks V + 4 yang valid dengan menerapkan penambahan 4 jalur ke grafik pelengkap vertex V yang valid.

Itu dimulai dengan memvalidasi input untuk mengonfirmasi keberadaan grafik komplementer yang valid (menggunakan n*~-n/4%1), dan jika itu gagal, kembali0 . Kemudian memeriksa apakah n>5dan berulang ke n-4kasus untuk membangun solusi urutan rendah yang valid, kemudian menerapkan 4-penambahan ke daftar adjacency kembali dalam perjalanan kembali rantai rekursi. Terakhir, jika n>5tidak benar, ia beralih dari 0ke n-1untuk xdan y, dan memeriksa apakah (y>>x)&1itu benar. Jika demikian, maka simpul-simpul tersebut dipasangkan.

Berikut ini adalah format fungsi yang lebih mudah dibaca, dengan operator ternary diperluas ke if-else statement dan eval()s inlined:

// precalculate amount of required vertices in v
f = (n, a = [], v = n*~-n / 4) => {
  // if amount is non-integer
  if (v % 1) {
    // no valid complementary graph
    return 0;
  } else {
    if (n > 5) {
      // generate valid (n-4)-order complementary graph
      f(n -= 4, a);
      // apply 4-path addition
      for (i = 0; i < n;)
        a.push([i, n+1],[i++, n+2]);
      a.push([n, ++n], [n, ++n], [n, ++n]);
    } else {
      // construct Rado graph using BIT predicate
      for(l = x = 0; x < n; x++)
        for(y = x; y < n; y++)
          // if amount of pairs is less than required and xth bit of y is high
          if (l < v && (y>>x & 1))
            // vertices x and y should be paired
            a.push([x,y]);
    }
    return a;
  }
};

Demo

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

<input type="number" onchange="o.textContent=JSON.stringify(f(this.value))"><pre id="o"></pre>