TUGAS
DEFINISI
Pertimbangkan poin {1,2,3,4,5} dan semua permutasi mereka. Kita dapat menemukan jumlah total kemungkinan permutasi dari 5 poin ini dengan trik sederhana: Imaging mengisi 5 slot dengan poin-poin ini, slot pertama akan memiliki 5 angka yang mungkin, 4 yang kedua (seperti yang telah digunakan untuk mengisi slot pertama) 3 ketiga dan seterusnya. Dengan demikian jumlah total Permutasi adalah 5 * 4 * 3 * 2 * 1; ini akan menjadi 5! permutasi atau 120 permutasi. Kita dapat menganggap ini sebagai grup simetris S5, dan kemudian Grup Simetri Sn akan memiliki n! or (n*n-1*n-2...*1)
permutasi.
Permutasi "genap" adalah permutasi di mana ada jumlah genap dari siklus panjang genap. Paling mudah dipahami ketika ditulis dalam notasi siklik, misalnya (1 2 3)(4 5)
permutasi 1->2->3->1
dan 4->5->4
dan memiliki satu siklus 3 panjang (1 2 3)
dan satu siklus 2 panjang (4 5)
. Saat mengklasifikasikan permutasi sebagai ganjil atau genap kami mengabaikan siklus panjang ganjil dan mengatakan bahwa permutasi ini [ (1 2 3)(4 5)
] ganjil karena memiliki bilangan ganjil {1} dari siklus panjang genap. Bahkan contoh:
(1)(2 3)(4 5)
= dua 2 siklus panjang | BAHKAN |(1 2 3 4 5)
= tidak ada siklus panjang | BAHKAN | * perhatikan bahwa jika tidak ada siklus panjang yang hadir maka permutasi adalah genap.
Contoh Aneh:
(1 2)(3 4 5)
= satu siklus 2 panjang | GANJIL |(1)(2 3 4 5)
= satu siklus 4 panjang | GANJIL |
Tepatnya setengah dari permutasi dalam Grup Symmetric mana pun bahkan kita dapat memanggil grup genap sebagai Alternating Group N, Sehingga S5 = 120 A5 = 60 permutasi.
PEMBERITAHUAN
Permutasi, setidaknya untuk ini, harus ditulis dalam notasi siklik di mana setiap siklus dalam kurung yang berbeda dan setiap siklus berjalan dalam urutan menaik. Misalnya (1 2 3 4 5)
tidak (3 4 5 1 2)
. Dan untuk siklus dengan angka tunggal, seperti: (1)(2 3 4)(5)
titik tunggal / tetap dapat dikecualikan artinya (1)(2 3 4)(5) = (2 3 4)
. Tetapi identitas {titik di mana semua titik ditetapkan (1)(2)(3)(4)(5)
} harus ditulis ()
hanya untuk mewakilinya.
TANTANGAN
Saya ingin Anda, dalam kode sesedikit mungkin, mengambil bilangan bulat positif sebagai input {1,2,3,4 ...} dan menampilkan semua permutasi dari Alternating Group An di mana n adalah input / semua bahkan permutasi dari Sn. Sebagai contoh:
Input = 3
()
(1 2 3)
(1 3 2)
dan
Input = 4
()
(1 2)(3 4)
(1 3)(2 4)
(1 4)(2 3)
(1 2 3)
(1 3 2)
(1 2 4)
(1 4 2)
(1 3 4)
(1 4 3)
(2 3 4)
(2 4 3)
Dan seperti dalam contoh saya ingin semua siklus dari satu panjang untuk dieliminasi, dan untuk identitas: output apa - apa,
()
{tidak hanya tanda kurung tetapi dengan apa pun yang Anda gunakan untuk menunjukkan permutasi yang berbeda} atau id
dapat diterima.
BACAAN EKSTRA
Anda dapat menemukan informasi lebih lanjut di sini:
SEMOGA BERHASIL
Dan karena ini adalah codegolf, siapa pun yang dapat mencetak permutasi Alternating Group An dalam byte terpendek, akan menang.
sumber
[[1, 2], [3, 4]]
bukan(1 2)(3 4)
?(2 3 1 4)
dalam urutan menaik? Maksudmu kita harus meletakkan elemen terkecil di depan?(2 3 1 4)
tidak2->3->1->4->2
dapat ditulis(1 4 2 3)
dengan elemen terkecil pertamaJawaban:
Pyth, 26 byte
Cobalah online
Solusi ini didasarkan pada penataan yang rapi antara permutasi dalam notasi satu baris dan permutasi dalam notasi siklus. Tentu saja, ada anggapan jelas di mana kedua notasi tersebut mewakili permutasi yang sama:
[8, 4, 6, 3, 10, 1, 5, 9, 2, 7] = (1 8 9 2 4 3 6) (5 10 7)
tetapi itu akan mengambil terlalu banyak kode. Alih-alih, cukup potong notasi satu baris menjadi beberapa bagian sebelum semua angka yang lebih kecil dari semua pendahulunya, sebut siklus potongan ini, dan buat permutasi baru darinya.
[8, 4, 6, 3, 10, 1, 5, 9, 2, 7] ↦ (8) (4 6) (3 10) (1 5 9 2 7)
Untuk membalikkan bijih ini, kita dapat mengambil permutasi apa pun dalam bentuk siklus, memutar setiap siklus sehingga jumlah terkecilnya adalah yang pertama, mengurutkan siklus sehingga jumlah terkecilnya muncul dalam urutan menurun, dan menghapus semua tanda kurung.
sumber
id
. Mungkin dia bisa berpadu?Mathematica,
844931 byteKomposisi dua fungsi. Output dalam bentuk yang
{Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}
mewakili(), (a b), (c d)(e f), ...
.sumber
J , 53 byte
Siklus di setiap permutasi diwakili sebagai array kotak karena J akan zero-pad array yang compang-camping.
Jika outputnya santai, gunakan 41 byte
di mana setiap permutasi dapat berisi satu siklus dan nol siklus.
Pemakaian
Untuk implementasi alternatif,
sumber
Jelly ,
3428 byteCoba di sini .
Penjelasan
Setiap baris dalam program Jelly mendefinisikan fungsi; yang paling bawah adalah "
main
".Baris pertama mendefinisikan fungsi yang menguji apakah suatu produk siklus aneh.
Baris kedua menormalkan partisi permutasi
[1…n]
menjadi produk siklus sebagai berikut:Ini akan mengubah misalnya
(4 3)(2 5 1)
menjadi(1 2 5)(3 4)
.Inilah program utamanya. Dibutuhkan argumen
n
dari baris perintah, dan:sumber
JavaScript (Firefox 30-57),
220218212211 byteSedihnya, 88 byte hanya cukup untuk menghasilkan grup bolak-balik sebagai daftar permutasi
a
, jadi saya perlu biaya tambahan132130124123 byte untuk mengkonversi output ke format yang diinginkan:Saya telah berhasil memotong versi ES6 saya ke
222216215 byte:sumber
(1,2,3)(4,5)
- itu permutasi aneh! Saat ini saya akan menunjukkan misalnya(1,2,3)(4)(5)
- tidak hanya menghapus siklus panjang satu biaya saya 6 byte saya kemudian berakhir dengan hasil kosong untuk siklus identitas yang akan saya biaya 4 byte lagi untuk memperbaikinya.as for the identity outputs of nothing ... are accepatble
. Dan juga apa yang akan ditampilkan jika Anda menampilkan "data mentah" Anda, apakah itu muncul dalam bentuk (1,2,3) (4) (5) atau sebagai sesuatu yang lain?[1, 2, 0, 3, 4]
contoh khusus itu, jadi tidak dekat dengan yang Anda inginkan.GAP , 32 byte
Terima kasih kepada @ChristianSievers karena memotong hitungan menjadi dua.
Penggunaan saat diminta:
sumber
f:=n->List(AlternatingGroup(n));