Pertimbangkan permutasi bilangan bulat 1
, ... n
,, seperti ini untuk n = 6
:
[5,2,4,3,6,1]
Jika Anda melihat permutasi sebagai pemetaan dari [1,2,3,4,5,6]
ke [5,2,4,3,6,1]
, permutasi dapat didekomposisi menjadi siklus terpisah . Siklus adalah subset elemen yang saling memetakan. Misalnya, 1
dipetakan ke 5
, yang dipetakan ke 6
, yang dipetakan kembali ke 1
. Jadi satu siklus [1,5,6]
. Siklus lainnya adalah [2]
dan [3,4]
. Jadi jumlah siklus untuk permutasi ini adalah 3
.
Secara umum, siklus permutasi adalah unik (sesuai pesanan), dan jumlah siklus untuk permutasi ukuran n
bervariasi dari 1
hingga n
.
Tantangan
Dengan permutasi yang tidak kosong, outputkan jumlah siklusnya.
Input adalah sebuah array yang dibentuk oleh n
bilangan bulat 1
, 2
, ..., n
, mana n > 0
. Setiap bilangan bulat terjadi tepat satu kali. Urutan di mana mereka muncul mendefinisikan permutasi, seperti pada contoh di atas.
Alih-alih array, Anda dapat menggunakan daftar, string dengan pemisah antara angka, input terpisah untuk setiap angka, atau apa pun yang masuk akal.
Untuk permutasi ukuran n
, bukannya set integer berbasis 1 1
, ..., n
Anda dapat secara konsisten menggunakan set berbasis 0 0
, ..., n-1
. Jika demikian, harap tunjukkan dalam jawaban Anda.
Kode harus bekerja n
hingga 20
waktu yang wajar, katakanlah kurang dari satu menit.
Golf kode. Semua bawaan diizinkan.
Uji kasus
Ini mengasumsikan input array berbasis 1.
[1] -> 1
[3,2,1] -> 2
[2,3,4,5,1] -> 1
[5,2,4,3,6,1] -> 3
[8,6,4,5,2,1,7,3] -> 2
[4,5,11,12,7,1,3,9,10,6,8,2] -> 1
[4,2,5,11,12,7,1,3,9,10,6,8] -> 5
[5,8,6,18,16,9,14,10,11,12,4,20,15,19,2,17,1,13,7,3] -> 3
[14,5,17,15,10,18,1,3,4,13,11,16,2,12,9,7,20,6,19,8] -> 7
Terkait
Tantangan terkait ini menanyakan siklus aktual dari permutasi, bukan jumlah mereka. Hanya membutuhkan jumlah siklus yang dapat menyebabkan algoritma yang lebih pendek yang menghindari menghasilkan siklus yang sebenarnya.
sumber
1
, ...,n
dalam urutan itu. Bisakah Anda mengklarifikasi bagaimana pemetaan bisa menjadi input? Apakah ini struktur data?dict
. Saya ingin memiliki{1: 2, 2: 1}
sebagai input, bukan[2, 1]
.Jawaban:
J, 4 byte
Ini mengasumsikan bahwa permutasi berbasis 0. Ini menggunakan builtin
C.
yang diberikan daftar yang mewakili permutasi langsung menghasilkan daftar siklus. Kemudian#
disusun@
berdasarkan yang mengembalikan jumlah siklus dalam daftar itu.Coba di sini.
sumber
JavaScript,
9998 byteSolusi ini mengasumsikan array dan nilainya diindeks nol (misalnya
[2, 1, 0]
).Penjelasan
sumber
Mathematica, 45 byte
Ini menghasilkan grafik dan menghitung komponen yang terhubung.
sumber
Mathematica,
372827 byteTerima kasih @alephalpha untuk menghemat 9 byte, dan @miles untuk 1 byte lagi.
sumber
PermutationCycles[#,Length]&
PermutationCycles
bisa mengambil argumen kedua untuk mengubah kepala outputnya. Anda juga dapat menggunakan notasi infiks untuk menyimpan byte lain#~PermutationCycles~Length&
.#&
agak sedikit lebih pendek dariIdentity
. ;)Python,
776967 bytesumber
(not p[i-1])
dapat dilakukan sebagai0**p[i-1]
Jelly,
12109 byteDisimpan 1 byte berkat @ Dennis .
Ini menggunakan permutasi berbasis 1. Ia bekerja dengan menerapkan permutasi berulang kali hingga mencapai permutasi sebelumnya sambil juga menjaga nilai sebelumnya. Dengan melacak perubahan, itu akan membuat orbit untuk setiap nilai di sepanjang kolom tabel itu. Kemudian, dengan menemukan minimum atau maksimum setiap kolom, label untuk siklus itu dapat dibuat. Kemudian deduplicate daftar label itu dan dapatkan panjangnya yang akan menjadi jumlah siklus terpisah.
Coba di sini.
Penjelasan
sumber
ị³$ÐĿ«/QL
harus bekerja.Python, 64 byte
Kode golf ini kebetulan idiomatis dan dapat dibaca. Menggunakan pengindeksan 0.
Setiap nilai melihat pada apa yang ditunjukkannya dan menunjuk ke nilai mana, dan menunjuk ke yang lebih kecil dari keduanya. Setelah pengulangan yang cukup, setiap elemen menunjuk ke elemen terkecil dari siklusnya. Jumlah elemen berbeda yang ditunjukkan adalah jumlah siklus.
Cukup untuk melakukan
n
iterasi. Atau, kita bisa mengulanginya sampai daftar tidak lagi berubah. Strategi ini memberi saya fungsi rekursif dengan panjang yang sama, 64 byte:Mengurangi adalah 65 byte
The
set(_)
konversi dapat dipersingkat untuk{*_}
Python 3.5, menyimpan 2 bytes.sumber
Haskell, 111 byte
Menggunakan pengindeksan berbasis 0
sumber
1l!i|iIi!!1ll1|
Pyth, 9 byte
Menggunakan indeks berbasis 0. Cobalah online .
Bagaimana itu bekerja
sumber
JavaScript (ES6), 49 byte
Menggunakan pengindeksan berbasis nol. Penjelasan:
reduce
digunakan untuk memanggil fungsi bagian dalamg
pada setiap elemen array.c
adalah hitungan siklus,e
adalah elemen array,i
adalah indeks array. Jika elemen kurang dari indeks, maka itu merupakan siklus potensial - elemen tersebut digunakan untuk mengindeks ke dalam array untuk menemukan elemen berikutnya dalam siklus secara rekursif. Jika kami memulai atau berakhir dengan indeks asli maka ini adalah siklus baru dan kami menambah hitungan siklus. Jika suatu saat kami menemukan nilai yang lebih besar dari indeks maka kami akan menghitung siklus itu nanti.sumber
[2,1,0,3,4,5]
, itu crash dengan pesan ini "Ukuran stack panggilan maksimum terlampaui".C, 90 byte
Panggil
f()
denganint
array yang bisa berubah , 1 pengindeksan berbasis. Parameter kedua adalah ukuran array. Fungsi mengembalikan jumlah siklus.Cobalah di ideone .
Algoritma:
sumber
GAP , 30 byte
Terus terang, argumen kedua untuk
Cycles
memberikan set di mana permutasi harus bertindak:sumber