Cetak permutasi "genap" dari grup simetris Sn dalam notasi siklik

9

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->1dan 4->5->4dan 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. (1)(2 3)(4 5)= dua 2 siklus panjang | BAHKAN |
  2. (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. (1 2)(3 4 5)= satu siklus 2 panjang | GANJIL |
  2. (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 iddapat 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.

Harry
sumber
2
Selamat Datang di Programming Puzzles dan Code Golf! Biasanya, kami mengizinkan output menjadi fleksibel, sehingga bahasa yang memiliki masalah dengan keluaran dalam format yang tepat tidak memiliki kerugian yang tidak adil. Apakah itu diperbolehkan untuk output misalnya, [[1, 2], [3, 4]]bukan (1 2)(3 4)?
Adnan
@ Adnan Ya, saya harus mengklarifikasi. Selama siklus yang berbeda ditampilkan secara terpisah seharusnya tidak ada masalah dengan bagaimana Anda telah mewakili ini.
Harry
"Permutasi" genap "adalah permutasi di mana ada permutasi genap genap." Ini terlihat seperti definisi siklik. Mungkin memperkenalkan notasi siklus terlebih dahulu dan kemudian menulis ulang kalimat itu menjadi "... jumlah siklus genap"?
Martin Ender
Juga, bagaimana saya menempatkan siklus (2 3 1 4)dalam urutan menaik? Maksudmu kita harus meletakkan elemen terkecil di depan?
Martin Ender
@MartinEnder Ya elemen terkecil harus pergi dulu selama itu tidak main-main dengan pesanan, sehingga (2 3 1 4)tidak 2->3->1->4->2dapat ditulis (1 4 2 3)dengan elemen terkecil pertama
Harry

Jawaban:

5

Pyth, 26 byte

t#Mf%+QlT2mcdf<>dTS<dTd.pS

          m            .pSQ   Map over permutations d of [1, …, Q]:
             f        d         Find all indices T in [1, …, Q] such that
               >dT                the last Q-T elements of d
              <   S<dT            is less than the sorted first T elements of d
           cd                   Chop d at those indices
   f                          Filter on results T such that
      Q                         the input number Q
     + lT                       plus the length of T
    %    2                      modulo 2
                                is truthy (1)
t#M                           In each result, remove 0- and 1-cycles.

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.

Anders Kaseorg
sumber
OP membutuhkan permutasi identitas untuk diwakili tanpa satu siklus. Saya pikir itu akan lebih baik jika bukan itu masalahnya.
mil
1
Harry sepertinya menyetujui jawaban Jelly-ku, yang mencetak 1 siklus bahkan untuk id. Mungkin dia bisa berpadu?
Lynn
Saya tidak begitu yakin dengan cara kata itu diucapkan, dan saya tidak memperhatikan bahwa solusi Anda (Lynn) juga melakukan hal yang sama.
mil
Pemahaman saya adalah bahwa Anda tidak dapat mewakili permutasi identitas menggunakan string kosong, jadi saya mengubah jawaban saya untuk menjaga semua 1-siklus (juga menghemat 6 byte).
Neil
1
Saya telah mengedit pertanyaan saya menjadi lebih jelas, saya ingin "satu siklus" untuk dihapuskan seperti yang telah Anda lakukan di bagian kedua dari jawaban Anda. Yang dilakukan dengan baik.
Harry
6

Mathematica, 84 49 31 byte

GroupElements@*AlternatingGroup

Komposisi dua fungsi. Output dalam bentuk yang {Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}mewakili (), (a b), (c d)(e f), ....

LegionMammal978
sumber
3

J , 53 byte

[:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]

Siklus di setiap permutasi diwakili sebagai array kotak karena J akan zero-pad array yang compang-camping.

Jika outputnya santai, gunakan 41 byte

[:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]

di mana setiap permutasi dapat berisi satu siklus dan nol siklus.

Pemakaian

   f =: [:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]
   f 3
┌┬───────┬───────┐
││┌─────┐│┌─────┐│
│││1 2 3│││1 3 2││
││└─────┘│└─────┘│
└┴───────┴───────┘
   f 4
┌┬───────┬───────┬─────────┬───────┬───────┬───────┬───────┬─────────┬───────┬───────┬─────────┐
││┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌───┬───┐│
│││2 3 4│││2 4 3│││1 2│3 4│││1 2 3│││1 2 4│││1 3 2│││1 3 4│││1 3│2 4│││1 4 2│││1 4 3│││2 3│1 4││
││└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└───┴───┘│
└┴───────┴───────┴─────────┴───────┴───────┴───────┴───────┴─────────┴───────┴───────┴─────────┘

Untuk implementasi alternatif,

   f =: [:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]
   f 3
┌─────┬─┬─┐
│1    │2│3│
├─────┼─┼─┤
│1 2 3│ │ │
├─────┼─┼─┤
│1 3 2│ │ │
└─────┴─┴─┘
mil
sumber
Ini sebenarnya indah ... dilakukan dengan baik.
Harry
2

Jelly , 34 28 byte

L€’SḂ
ṙLR$Ṃµ€Ṣ
Œ!ŒṖ€;/Ç€ÑÐḟQ

Coba 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.

    L€      Length of each
      ’     Add 1 to each length 
       S    Take the sum
        Ḃ   Modulo 2
    
  • Baris kedua menormalkan partisi permutasi [1…n]menjadi produk siklus sebagai berikut:

         µ€    For each list X in the partition:
    ṙLR$          Rotate X by each element in [1…length(X)].
        Ṃ         Get the lexicographically smallest element.
                  Thus, find the rotation so that the smallest element is in front.
           Ṣ   Sort the cycles in the partition.
    

    Ini akan mengubah misalnya (4 3)(2 5 1)menjadi (1 2 5)(3 4).

Inilah program utamanya. Dibutuhkan argumen ndari baris perintah, dan:

Œ!              Compute all permutations of [1…n].
  ŒṖ€           Compute all partitions of each permutation.
     ;/         Put them in one big list.
       ǀ       Normalize each of them into a cycle product.
         ÑÐḟ    Reject elements satisfying the top function,
                i.e. keep only even cycle products.
            Q   Remove duplicates.
Lynn
sumber
Saya mencoba menjalankannya dengan 5 sebagai input, dan tidak mendapatkan output sama sekali. Apakah skrip ini hanya untuk Grup A3 dan A4 atau dapatkah berpotensi memberikan grup apa pun? Saya belum pernah melihat Jelly sebelumnya sehingga penjelasan apa pun akan sangat membantu.
Harry
Tidak, saya hanya menempatkan 3 dan 4 di tantangan begitu, sejauh ini Anda menang tetapi saya benar-benar hanya ingin belajar lebih banyak.
Harry
Jelly sebenarnya memiliki built-in untuk partisi, yang saya lupa! Syukurlah, seorang teman mengingatkan saya. Jadi sekarang lebih efisien (menangani n = 5, yay!) Dan lebih pendek.
Lynn
OP telah mengedit pertanyaan untuk mengklarifikasi bahwa 1 siklus harus dielakkan.
Anders Kaseorg
2

JavaScript (Firefox 30-57), 220 218 212 211 byte

f=(a,p)=>a[2]?[for(i of a)for(j of f(a.filter(m=>m!=i),p,p^=1))[i,...j]]:[[a[p],a[p^1]]]

Sedihnya, 88 byte hanya cukup untuk menghasilkan grup bolak-balik sebagai daftar permutasi a, jadi saya perlu biaya tambahan 132 130 124 123 byte untuk mengkonversi output ke format yang diinginkan:

n=>f([...Array(n).keys()],0).map(a=>a.map((e,i)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&s)

Saya telah berhasil memotong versi ES6 saya ke 222 216 215 byte:

n=>(g=(a,p,t=[])=>a[2]?a.map(e=>g(a.filter(m=>m!=e),p,[...t,e],p^=1)):[...t,a[p],a[p^1]].map((e,i,a)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&r.push(s))([...Array(n).keys(r=[])],0)&&r
Neil
sumber
Saya tidak keberatan jika formatnya tidak dalam notasi siklik sempurna selama: setiap permutasi dan siklusnya ditampilkan terpisah (seperti [1 2 3] [4 5] dan <<123> <45>> keduanya akan diterima ) dan siklus satu panjang diputuskan. Mungkin ini dapat mempersingkat jawaban Anda
Harry
@ Harry, aku tidak pernah menunjukkan (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.
Neil
Jika Anda berarti tidak ada yang dicetak untuk identitas maka saya akan menerimanya seperti yang saya katakan 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?
Harry
@ Harry Sekarang tidak termasuk siklus panjang satu, termasuk entri kosong untuk identitas, dan masih berhasil menghemat satu byte!
Neil
@Harry Raw data akan menjadi [1, 2, 0, 3, 4]contoh khusus itu, jadi tidak dekat dengan yang Anda inginkan.
Neil
1

GAP , 32 byte

Terima kasih kepada @ChristianSievers karena memotong hitungan menjadi dua.

f:=n->List(AlternatingGroup(n));

Penggunaan saat diminta:

gap> f(4);
[ (), (1,3,2), (1,2,3), (1,4,3), (2,4,3), (1,3)(2,4), (1,2,4), (1,4)(2,3), (2,3,4), (1,3,4), (1,2)(3,4), (1,4,2) ]
Liam
sumber
Pemformatan yang sangat bagus, saya pikir GAP adalah pilihan yang sangat baik untuk menjawab masalah ini.
Harry
Jawaban Anda tidak menunjukkan di mana satu permutasi berakhir dan yang berikutnya dimulai. Dengan asumsi fungsi tidak perlu mencetak nilai-nilai sebagai efek samping, tetapi mungkin hanya mengembalikan nilai sebagai daftar yang akan dicetak oleh penerjemah, saya akan lakukanf:=n->List(AlternatingGroup(n));
Christian Sievers