Dengan dua permutasi dalam bentuk siklus disjoint, output produk / komposisinya dalam bentuk siklus disjoint.
Untuk menemukan komposisi, konversi siklus terpisah menjadi permutasi dalam notasi dua baris. Setiap angka di bagian yang terpisah dari suatu siklus dipetakan ke nomor yang mengikutinya di bagian yang sama. Itu membungkus. Jadi 1 -> 5
, 5 -> 1
, 2 -> 4
, 4 -> 2
. Jika nomor tidak ditemukan 3 -> 3
, maka dipetakan ke dirinya sendiri. Siklus saling lepas pertama juga bisa ditulis (1 5)(2 4)(3)
. Pemetaan ini dikonversikan menjadi dua baris, seperti demikian (perhatikan bahwa urutan P dan Q terbalik):
[T] he produk dari dua permutasi diperoleh dengan mengatur ulang kolom dari permutasi kedua (paling kiri) sehingga baris pertama identik dengan baris kedua dari permutasi pertama (paling kanan). Produk kemudian dapat ditulis sebagai baris pertama dari permutasi pertama di atas baris kedua dari permutasi kedua yang dimodifikasi.
Aturan:
- Input akan diberikan sebagai daftar daftar atau format serupa
- Anda mungkin tidak mengambil sesuatu seperti
(1 5)(2 4)
seperti[5, 4, 3, 2, 1]
, sudah dalam bentuk dua-line (indeks pemetaan nilai) - Tidak semua angka harus muncul di setiap grup, jadi Anda bisa
(1 5)·(1 2)
, menghasilkan(2 5 1)
. - Output Anda harus dapat digunakan sebagai input Anda.
- Anda tidak perlu mendukung input dengan siklus kosong
(1 5)·()
. Yang sebaliknya akan diberikan sebagai(1 5)·(1)
atau sesuatu yang setara. - Karena siklus membungkus, urutannya tidak masalah asalkan hasilnya benar.
- Anda bisa mulai dari nol atau satu. Tidak masalah, karena hasilnya sama.
- Jumlahnya bisa lebih besar dari
9
. - Anda mungkin tidak memasukkan angka yang sama lebih dari sekali dalam output. Jadi
[[1],[1]]
tidak diijinkan. - Perhatikan bahwa operasi ini tidak komutatif ! Saya menempatkan Q di depan P, karena itulah yang dilakukan Wikipedia. Anda dapat memilih pesanan apa pun, tetapi tentukan yang mana jika berbeda.
- Kode terpendek menang
- Built-in diizinkan, tetapi jika Anda menggunakannya, tunjukkan solusi tanpa menggunakannya juga.
Contoh:
Tidak semua kemungkinan output setara ditampilkan
Input
Output
[[1, 5], [2, 4]], [[1, 2, 4, 3]]
[[1, 4, 3, 5]] (or [[4, 3, 5, 1]] or ...)
[[1, 5]], [[1, 2]]
[[2, 5, 1]]
[[10, 2, 3]], [[2]]
[[3, 10, 2]]
[[1]], [[3]]
[[]] (or [[1]] or something equivalent)
[[10,2,3,15],[1,7],[5,6],[14,4,13,11,12]], [[5,6,7,9,14],[2,8,3,10],[1,11]]
[[12, 14, 6, 1], [8, 15, 10, 3, 2], [13, 11, 7, 9, 4]]
(arguments in reverse order from above gives a different answer)
[[5,6,7,9,14],[2,8,3,10],[1,11]], [[10,2,3,15],[1,7],[5,6],[14,4,13,11,12]]
[[9, 14, 4, 13, 1], [10, 8, 3, 15, 2], [7, 11, 12, 5]]
sumber
Jawaban:
J , 7 byte
Cobalah online!
sumber
Mathematica, 15 byte
Ya Virginia, ada builtin .... Mathematica mendukung tipe data permutasi yang sudah dalam notasi siklus terpisah: fungsi murni ini mengambil sebagai input sejumlah argumen dalam bentuk
Cycles[{{1, 5}, {2, 4}}]
dan output permutasi produk, lagi dalamCycles[]
bentuk. Ini menggunakan konvensi pemesanan yang berlawanan sebagai OP, jadi misalnya,kembali
Cycles[{{1, 4, 3, 5}}]
. The⊙
simbol saya gunakan di atas harus benar-benar menjadi 3-byte swasta penggunaan Unicode simbol U + F3DE untuk bekerja di Mathematica. Perhatikan bahwa Mathematica memiliki builtin bernama untuk operasi iniPermutationProduct
, tetapi itu tiga byte lebih lama.sumber
Haskell ,
157148 byteEDIT:
p++q
. Urutan argumen bertukarg
. Dihilangkand
dengan memulaiiterate
denganp x
, setelah itutakeWhile
tidak lagi diikat denganfst
+span
. Dibuatiterate
infiks.Melakukan ini ketika saya terlambat ... mungkin bisa bermain golf lagi.
Itu lebih sederhana, dan tampaknya diizinkan, sehingga output mencakup siklus elemen tunggal.
Cobalah online!
Bagaimana itu bekerja:
#
adalah fungsi utama.q#p
mengambil dua daftar daftar angka, dan mengembalikan daftar serupa. Tes tampaknya memiliki Q sebelum P jadi saya menggunakan urutan yang sama.f p
mengubah permutasip
dari bentuk siklus disjoint ke fungsi, setelah ituf q
danf p
dapat disusun dengan operator komposisi biasa.
.c
, mencaria
dan menemukan penggantinya. Jika pemahaman tidak menemukan apa pun,a
baru dikembalikan.zip(0:c)(c++c)
adalah daftar pasangan elemenc
dan penerusnya. Karena pertanyaannya memungkinkan kita "mulai pada satu" kita dapat menggunakan0
sebagai nilai dummy; lebih murah untuk menambahkannya kezip
argumen pertama daripada menggunakan argumentail
kedua.g l p
mengambil daftarl
elemen, dan fungsi permutasip
, dan mengembalikan daftar siklus yang menyentuh elemen.c
adalah siklus yang mengandung elemen pertamax
dari daftar, elemen-elemen lainc
ditemukan dengan iterasi darip x
hinggax
ditemukan kembali. Ketika berulang-ulang untuk menemukan siklus yang tersisa, semua elemenc
pertama dihapus dengan pemahaman daftar.sumber
Python, 220 byte
sumber
Python 3.8 , 187 byte
Cobalah online! atau Periksa semua test case!
Input :
q
danp
dalam urutan itu, masing-masing adalah satu set tupel, dariSTDIN
.Output : Permutasi produk
Q·P
sebagai satu set tupel, untukSTDERR
.Penjelasan
Fungsi
g
menemukan nomor mana yang memetakan ke nomori
dalam permutasip
(aliasg
adalah permutasi terbalikp
).Fungsi
h
mengambil angka, dan mengembalikan siklusQ·P
yang berisi angka itu. Siklus yang dikembalikan akan menjadi tupel, diformat sedemikian rupa sehingga elemen terkecil berada di indeks 0.Dengan menerapkan
h
ke semua angka, kita bisa mendapatkan semua siklusQ·P
. Untuk mencegah duplikat siklus dalam hasil kami, kami cukup menaruh semua siklus dalam satu set. Ini bekerja karena siklus serupa yang dikembalikan olehh
akan diformat ke tuple yang sama (dengan elemen terkecil pada indeks 0).Kita hanya perlu mempertimbangkan angka yang muncul di
P
atauQ
, karena semua nomor lain akan dipetakan ke diri mereka sendiri.sumber