Konjugasi permutasi

17

Permutasi ukuran n adalah penataan ulang bilangan bulat n positif pertama . (artinya setiap integer muncul sekali dan tepat sekali). Permutasi dapat diperlakukan seperti fungsi yang mengubah urutan daftar item berukuran n . Sebagai contoh

(4 1 2 3) ["a", "b", "c", "d"] = ["d", "a", "b", "c"]

Dengan demikian permutasi dapat disusun seperti fungsi.

(4 1 2 3)(2 1 3 4) = (4 2 1 3)

Ini menghasilkan banyak properti menarik. Hari ini kami fokus pada konjugasi . Permutasi y dan x (keduanya ukuran n ) adalah konjugat jika jika ada permutasi g dan g -1 (juga ukuran n ) sedemikian rupa sehingga

x = gyg-1

dan gg -1 sama dengan permutasi identitas ( angka n pertama dalam urutan yang benar).

Tugas Anda adalah mengambil dua permutasi dengan ukuran yang sama melalui metode input standar dan memutuskan apakah keduanya merupakan konjugat. Anda harus menampilkan salah satu dari dua nilai yang konsisten, satu jika mereka konjugat dan yang lainnya jika tidak.

Ini adalah kode-golf sehingga jawaban akan dicetak dalam byte dengan lebih sedikit byte yang lebih baik.

Ada banyak teorema tentang permutasi konjugasi yang Anda inginkan, jadi semoga sukses dan senang bermain golf.

Anda dapat mengambil input sebagai wadah nilai yang terurut (baik 1-n atau 0-n) yang mewakili permutasi seperti di atas, atau sebagai fungsi yang mengambil wadah yang dipesan dan melakukan permutasi. Jika Anda memilih untuk mengambil fungsi, Anda harus menganggapnya sebagai argumen daripada menggunakannya dengan nama yang telah ditentukan.

Uji Kasus

(1) (1) -> True
(1 2) (2 1) -> False
(2 1) (2 1) -> True
(4 1 3 2) (4 2 1 3) -> True
(3 2 1 4) (4 3 2 1) -> False 
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -> True
code-golf decision-problem combinatorics permutations abstract-algebra Posting Rock Garf Hunter
sumber
Bisakah kita mengambil input sebagai fungsi? Bisakah kita juga mengambil ukuran n?
xnor
@ xnor Yakin pada kedua hal. Saya tidak yakin bagaimana yang pertama akan membantu Anda.
Posting Rock Garf Hunter
Aturan input fungsi default memungkinkan fungsi diasumsikan telah ditentukan sebelumnya, yang menyimpan byte saat menuliskannya sebagai argumen, jika Anda mengizinkannya.
xnor
@ xnor Apakah kita berbicara tentang aturan ini? Itu untuk fungsi kotak hitam yang permutasi tidak. Ini masuk akal karena konsensus itu dirancang untuk memungkinkan bahasa tanpa fungsi pointer / objek untuk bersaing sedangkan di sini mereka bisa karena permutasi dapat diwakili sebaliknya.
Posting Rock Garf Hunter
Saya, saya tidak berpikir perbedaan mereka menjadi kotak hitam. Jadi di sini, input mungkin merupakan fungsi, tetapi hanya sebagai argumen eksplisit?
xnor

Jawaban:

6

Python 2 , 87 byte

f=lambda P,k:k<1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&f(P,k-1)

Cobalah online!

Mengambil input dengan Psebagai pasangan permutasi dan kpanjangnya. Output 1untuk konjugat dan 0tidak.

Ini menggunakan hasil:

Dua permutasi x dan y adalah konjugat persis jika kekuatan k -th x k dan y k memiliki jumlah titik tetap yang sama untuk setiap k dari 0 hingga n .

Dua permutasi konjugasi memuaskan ini karena kekuatan k- th mereka juga konjugat, dan konjugasi mempertahankan jumlah titik tetap.

Tidak terlalu jelas bahwa dua permutasi non-konjugasi selalu berbeda. Secara khusus, konjugasi ditentukan oleh daftar panjang siklus yang diurutkan, dan ini dapat dipulihkan dari jumlah titik tetap. Salah satu cara untuk menunjukkan ini adalah dengan aljabar linier, meskipun mungkin berlebihan.

Biarkan X menjadi matriks permutasi untuk x . Kemudian, jumlah titik tetap x k adalah Tr (X k ) . Jejak ini adalah kekuatan jumlah polinomial simetris dari nilai eigen dari X k dengan keanekaragaman. Polinomial-polinomial ini untuk k dari 0 hingga n mari kita pulihkan polinomial simetris elementer yang sesuai dari nilai-nilai eigen ini, dan karenanya polinom karakteristik dan dengan demikian nilai eigen itu sendiri.

Karena nilai eigen ini adalah akar dari persatuan yang sesuai dengan siklus x , dari sini kita dapat memulihkan ukuran siklus dan multiplisitasnya. Jadi, "tanda tangan" kami mengidentifikasi permutasi hingga konjugasi.

Tidak
sumber
6

J , 25 byte 23 byte 16 byte

solusi mil diam - diam:

-:&([:/:~#&>)&C.

Solusi eksplisit OP:

c=:4 :'-://:~"1#&>C.&>x;y'

Ini memeriksa apakah permutasi x dan y memiliki jenis siklus yang sama, menggunakan C.fungsi bawaan untuk menghasilkan representasi siklus.

   4 1 3 2   c   4 2 1 3
1
   3 2 1 4   c   4 3 2 1
0
   2 1 3 4 5 7 6   c   1 3 2 5 4 6 7
1
Mathias Dolidon
sumber
1
Selamat datang di PPCG dan postingan pertama yang bagus. Saya mempersingkat metode Anda menjadi 16 byte -:&([:/:~#&>)&C.dengan menggunakan formulir diam-diam. Inilah tautan TIO untuk mencobanya.
mil
Terima kasih. :) Saya masih pemula, dan meskipun saya tampaknya mudah menggunakannya dengan bentuk eksplisit, menulis bentuk diam-diam yang efisien masih membutuhkan banyak pemikiran bagi saya. Saya akan menambahkan solusi Anda.
Mathias Dolidon
PS: bukankah kita menghitung karakter penugasan fungsi juga? c=:
Mathias Dolidon
1
@MathiasDolidon Tidak, berdasarkan konsensus default, kami tidak menghitung karakter yang diperlukan untuk penugasan, karena fungsi dapat digunakan apa adanya (dengan tanda kurung, tapi kami tidak menghitungnya).
Erik the Outgolfer
1
BAIK ! Saya telah memperbarui surut jumlah untuk solusi eksplisit dalam judul untuk memperhitungkan ini.
Mathias Dolidon
4

MATL , 20 19 17 16 byte

xY@!"&G@)@b)X=va

Input: dua vektor kolom (menggunakan ;sebagai pemisah). Output: 1jika konjugasi, 0jika tidak.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Tidak ada teorema tentang permutasi yang digunakan (karena ketidaktahuan belaka); hanya kekerasan dan dua fakta ini:

  • Untuk dua permutasi p dan q , komposisi pq setara dengan menggunakan p untuk mengindeks elemen-elemen q .

  • Kondisi x = gyg −1 setara dengan xg = gy .

Kode yang dikomentari:

x      % Implicitly input first permutation, x. Delete it. Gets copied into clipboard G
Y@     % Implicitly input second permutation, y. Push a matrix with all permutations
       % of its elements, each permutation on a different row. So each matrix row is
       % a permutation of [1 2 ...n], where n is the size of y
!      % Transpose. Now each permutation is a column
"      % For each column
  &G   %   Push x, then y
  @    %   Push current column. This is a candidate g permutation
  )    %   Reference indexing. This gives g composed with y
  @    %   Push current column again
  b    %   Bubble up. Moves x to the top of the stack
  )    %   Reference indexing. This gives x composed with g
  X=   %   Are they equal as vectors? Gives true or false
  v    %   Concatenate stack so far. The stack contains the latest true/false result
       %   and possibly the accumulated result from previous iterations
  a    %   Any: gives true if any element is true. This is the "accumulating" function
       % Implicit end. Implicit display
Luis Mendo
sumber
2

Jelly , 11 byte

Œ!©Ụ€ịị"®⁸e

Cobalah online!

Bagaimana itu bekerja

Œ!©Ụ€ịị"®⁸e  Main link. Left argument: x. Right argument: y

Œ!©          Take all permutations g of x. Copy the result to the register.
   Ụ€        Grade up each; sort the indices of each permutation g by their
             corresponding values. For permutations of [1, ..., n], grading up
             essentially computes the inverse, g⁻¹.
     ị       Let each g⁻¹ index into y, computing g⁻¹y.
      ị"®    Let the results index into the corresponding g, computing g⁻¹yg.
         ⁸e  Test if x occurs in the result.
Dennis
sumber
Sejauh yang saya mengerti, sebenarnya yyang mengindeks masing-masing g⁻¹, bukan sebaliknya. Lihat contoh (4 1 2 3)(2 1 3 4) = (4 2 1 3),. Dengan pendekatan Anda, itu akan menghasilkan (1 4 2 3)sebaliknya, karena indeks kedua menjadi yang pertama. Mempertimbangkan itu, saya punya solusi 12-byte yang belum saya rusak. :-)
Erik the Outgolfer
@EriktheOutgolfer Diperbaiki.
Dennis
@ Dennis Tapi saya tidak sampai pada kesimpulan itu berdasarkan pada penjelasan, saya tiba pada pendekatan yang sama persis, kecuali bahwa saya memiliki sesuatu seperti Œ!©Ụ€⁹ịЀ®ị"⁸e(pada dasarnya semua pengindeksan dengan argumen terbalik), kecuali lebih pendek setelah saya membuat modifikasi besar. Saya pikir tidak g⁻¹ygsama dengan gyg⁻¹. Juga, saya pikir jawaban Anda dapat mengambil manfaat dari modifikasi itu juga, tetapi, seperti yang saya katakan sebelumnya, saya belum ingin merusak kesenangannya.
Erik the Outgolfer
Ya, persis sama. Jika x = g⁻¹yg, maka gxg⁻¹ = y, xdan ykonjugat.
Dennis
Hm, saya merasa seperti saya harus mengungkapkan solusi 12-byte saya kemudian:eŒ!ị"Ụị@¥€¥¥
Erik the Outgolfer
1

Sekam , 9 byte

¤¦ṠmöLU¡!

Pengembalian 1untuk konjugasi dan 0untuk non-konjugat. Cobalah online!

Penjelasan

Kelas conjugacy dari permutasi P dari L = [1,2, .., n] ditentukan oleh multiset yang mengandung periode setidaknya setiap angka di L di bawah P . Ketika P diambil dalam format daftar, saya bisa mengganti L dengan P dan mendapatkan multiset yang sama. Program menghitung multiset yang sesuai untuk setiap input dan memeriksa apakah ada sub-multiset lainnya. Karena mereka memiliki jumlah elemen yang sama, ini setara dengan menjadi multiset yang sama.

¤¦ṠmöLU¡!  Implicit inputs: two lists of integers.
¤          Apply one function to both and combine with another function.
  ṠmöLU¡!  First function. Argument: a list P.
  Ṡm       Map this function over P:
       ¡!  iterate indexing into P,
      U    take longest prefix with unique elements,
    öL     take its length.
 ¦         Combining function: is the first list a subset of the other, counting multiplicities?
Zgarb
sumber
1

Perl, 61 58 57 byte

Termasuk +2untukap

Berikan permutasi berbasis 0 sebagai 2 baris pada STDIN

perl -ap '$_=[@1]~~[@1=map{-grep$_-$G[$i++%@G],@F=@G[@F]}@G=@F,0]'
3 0 2 1
3 1 0 2
^D

Algoritma adalah variasi kecil pada solusi satu di xnor

Versi yang lebih lama dari kode ini mengenai bug perl dan dump core untuk beberapa input pada perl terbaru saya 5.26.1, tetapi ia bekerja pada perl yang lebih lama 5.16.3.

@{$.}=map{-grep$_==$F[$i++%@F],@G=@F[@G]}@G=@F,0}{$_=@1~~@2

Itu mungkin contoh lain dari musuh perlgolf lama saya, fakta bahwa perl tidak menghitung ulang tumpukannya dengan benar.

Ton Hospel
sumber
1

JavaScript (ES6), 66 64 byte

(a,b,g=a=>b+a.map(h=(e,i)=>e-i&&1+h(a[e],i)).sort())=>g(a)==g(b)

Jika saya sudah membaca jawaban lain dengan benar, masalahnya sama dengan menghitung periode semua elemen dan memeriksa bahwa kedua daftar memiliki jumlah yang sama pada setiap periode. Sunting: Disimpan 1 byte berkat @Arnauld dengan menghitung satu kurang dari periode. Menyimpan byte lain berkat @Arnauld dengan menyalahgunakan aturan paksaan aneh JavaScript untuk membandingkan array. Byte lain bisa diselamatkan dengan kari tetapi saya tidak suka kari kecuali ayam tikka masala.

Neil
sumber