pengantar
Diberikan graf G tidak berarah, kita dapat membuat grafik L (G) (disebut grafik garis atau grafik konjugat) yang mewakili koneksi antara tepi dalam G. Ini dilakukan dengan membuat simpul baru di L (G) untuk setiap tepi di G dan menghubungkan simpul-simpul ini jika ujung-ujungnya mewakili memiliki simpul yang sama.
Berikut adalah contoh dari Wikipedia yang menunjukkan pembuatan grafik garis (berwarna hijau).
Sebagai contoh lain, ambil grafik G ini dengan simpul A, B, C, dan D.
A
|
|
B---C---D---E
Kami membuat simpul baru untuk setiap tepi di G. Dalam hal ini, tepi antara A dan C diwakili oleh simpul baru yang disebut AC.
AC
BC CD DE
Dan hubungkan simpul ketika tepi yang mereka wakili memiliki titik yang sama. Dalam hal ini, ujung-ujungnya dari A ke C dan dari B ke C memiliki titik sudut C yang sama, sehingga simpul AC dan BC terhubung.
AC
/ \
BC--CD--DE
Grafik baru ini adalah grafik garis G!
Lihat Wikipedia untuk informasi lebih lanjut.
Tantangan
Dengan diberikan daftar adjacency untuk grafik G, program Anda harus mencetak atau mengembalikan daftar adjacency untuk grafik garis L (G). Ini kode-golf, jadi jawabannya dengan byte paling sedikit menang!
Memasukkan
Daftar pasangan string yang mewakili tepi G. Setiap pasangan menggambarkan simpul yang terhubung dengan tepi itu.
- Setiap pasangan (X, Y) dijamin unik, artinya daftar tidak akan berisi (Y, X) atau yang kedua (X, Y).
Sebagai contoh:
[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]
Keluaran
Daftar pasangan string yang mewakili tepi L (G). Setiap pasangan menggambarkan simpul yang terhubung dengan tepi itu.
Setiap pasangan (X, Y) harus unik, artinya daftar tidak akan berisi (Y, X) atau yang kedua (X, Y).
Untuk setiap tepi (X, Y) dalam G, simpul yang dibuatnya dalam L (G) harus dinamai XY (nama-nama tersebut digabungkan bersama-sama dalam urutan yang sama seperti yang ditentukan dalam input).
Sebagai contoh:
[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]
Uji Kasus
[] -> []
[("0","1")] -> []
[("0","1"),("1","2")] -> [("01","12")]
[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]
[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
sumber
[("1","23"),("23","4"),("12","3"),("3","4")]
, yang hasilnya mungkin seharusnya[("123","234"),("123","34")]
, yang tidak dapat ditafsirkan dengan benar. Saya pikir satu-satunya cara untuk memperbaikinya adalah dengan mengedit dalam jaminan bahwa input tidak akan pernah mengandung ambiguitas seperti itu, tetapi jika pertanyaan ini telah diposting di kotak pasir maka saya akan menyarankan menjadi kurang preskriptif tentang penamaan simpul dalam output.Jawaban:
Ruby, 51 byte
Cobalah online!
Untuk setiap kombinasi dari dua tepi, jika mereka memiliki titik yang sama (yaitu jika elemen pertama dari persimpangan mereka adalah non-
nil
), cetak array yang berisi dua tepi ke STDOUT.sumber
JavaScript (Firefox 30-57), 77 byte
Asumsikan semua input adalah huruf tunggal (well, setiap karakter selain
^
dan]
).sumber
Brachylog , 13 byte
Cobalah online!
Dengan semua kasus uji
(-1 byte diganti
l₂
denganĊ
, terima kasih kepada @Fatalize.)sumber
Ċ
(pasangan) alih-alihl₂
menyimpan satu byte.K (ngn / k) ,
4539332930 byteCobalah online!
,:'
bungkus setiap sisi dalam daftar 1-elemen{
}@
menerapkan fungsi dengan argumen implisitx
x,/:\:x
menyatukan masing-masing kirix
dengan masing-masing kananx
, dapatkan matriks hasil - semua pasang tepi,/
ratakan matriks(
)#
Saring(3=#?,/)#
memfilter hanya pasangan yang rangkaian (,/
) memiliki jumlah (#
) tepat 3?
elemen unik ( )Ini menghilangkan tepi seperti
("ab";"ab")
dan("ab";"cd")
dari daftar.(*>)#
filter hanya pasangan yang permutasinya menurun (>
) dimulai dengan (*
) a 1 (bukan-0 adalah boolean true)Dalam kasus kami, permutasi sort-descending bisa
0 1
atau1 0
.sumber
Jelly , 5 byte
Cobalah online!
sumber
f
danƇ
digunakan dalam Jelly? Jika saya membacanya di dokumen, keduanya adalah filter.f
adalah " Filter; hapus elemen-elemen dari x yang tidak ada di dalam y. " danƇ
adalah " Filter (alias untukÐf
). Simpan semua item yang memenuhi syarat. ". Apakah mereka selalu digunakan bersama? ApakahƇ
digunakan untuk menutup filterf
? Seperti di,f...Ƈ
mirip denganʒ...}
di 05AB1E? Atau apakah/
(" Mengurangi atau mengurangi n-bijaksana. ") Ada hubungannya dengan itu? Hanya mencoba memahami kode, dan saya bingung dengan dua perintah filter yang berbeda (dan bagaimana keduanya digunakan di sini). :)f
danƇ
dua hal yang sepenuhnya terpisah. Anda dapat menganggapnyaf
sebagai persimpangan (diberi dua daftar, itu mengembalikan elemen umum mereka) danƇ
sepertiʒ
di 05AB1E. Singkatnya:Œc
mengembalikan semua kombinasi yang mungkin dari dua elemen dari daftar, kemudianƇ
hanya membuat mereka yang memenuhi tautan (yaitu fungsi Jelly)f/
, yang mengembalikan persimpangan dua item. Tetapif
adalah angka dua (fungsi dua argumen) dan kita perlu menerapkannya pada daftar dua elemen, jadi kita harus menggunakan/
, mengurangi.f
dalam dokumen, meskipun benar, terutama membingungkan saya dengan filter yang sebenarnyaƇ
digunakan. Penjelasan Anda tentang " diberikan dua daftar, kembalikan unsur-unsur umum mereka " membuat semuanya jelas. Dan saya memang merasa bahwa/
itu digunakan untuk mengkonversi data Jelly entah bagaimana. Sebenarnya, saya sekarang melihat bagian 6.6 Mengurangi dalam Tutorial pada wiki Jelly yang menjelaskan bagaimana itu muncul angka dua dan mendorong pengurangan monad (pada dasarnya 2 argumen vs daftar pasangan sebagai argumen). Terima kasih, semuanya jelas sekarang!MATL , 13 byte
Cobalah online!
Tidak seburuk yang saya harapkan diberi input array sel. Ide dasarnya sama dengan jawaban Ruby @ Doorknob .
sumber
C (gcc) , 173 byte
Input
i
dan outputo
adalah array datar, null-dihentikan. Nama keluaran bisa hingga 998 karakter jauh sebelum ini akan rusak.Cobalah online!
sumber
*x
alih-alihx[0]
danint**
bukannyachar**
Mathematica 23 byte
Contoh:
g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 }]
(*
{2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3}
*)
sumber
Pyth , 7 byte
Coba di sini!
Jika perlu bergabung, 10 byte
Coba di sini!
sumber
Bahasa Wolfram
6453 byteMenemukan semua daftar masukan dengan
Subset
panjang 2,Select
yaitu titik-titik di mana pasangan berpasangan bersilangan dengan pasangan berpasangan lainnya (yang menunjukkan bahwa pasangan berbagi sebuah simpul), danStringJoin
simpul untuk semua pasangan yang dipilih.Kode ini sangat sulit dibaca karena mempekerjakan 4 fungsi bersarang murni ( alias "anonim").
Kode ini menggunakan kurung kurawal, "{}", sebagai pembatas daftar, seperti biasa dalam Bahasa Wolfram.
1 byte disimpan berkat Tn. Xcoder.
Contoh
sumber
Select[#~Subsets~{2},IntersectingQ@@#&]/.{a_,b_}:>{""<>a,""<>b}&
- Cobalah online!Python 2 , 109 byte
Cobalah online!
Untuk setiap node
x
(ditemukan dengan membuat satu set dari daftar tepi rata), buat daftar pasanganp
yang memilikix
sebagai anggota; kemudian, untuk masing-masing daftar ituQ
, temukan pasangan unik dan berbeda di dalamQ
(keunikan / perbedaan diberlakukan melaluiif s<t
).sumber
C # 233 byte
Contoh
sumber