Jumlah siklus permutasi

23

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, 1dipetakan 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 nbervariasi dari 1hingga n.

Tantangan

Dengan permutasi yang tidak kosong, outputkan jumlah siklusnya.

Input adalah sebuah array yang dibentuk oleh nbilangan 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, ..., nAnda dapat secara konsisten menggunakan set berbasis 0 0, ..., n-1. Jika demikian, harap tunjukkan dalam jawaban Anda.

Kode harus bekerja nhingga 20waktu 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.

Luis Mendo
sumber
Nevermind pertanyaan saya, dinyatakan dalam pertanyaan 0 berbasis input diperbolehkan.
orlp
@ Atlp Itu cepat! Saya bahkan tidak bisa melihat pertanyaan Anda
Luis Mendo
Bisakah kita mengambil pemetaan indeks ke nilai sebagai input?
Tembaga
1
@ Kopper Saya pikir ya, jika domain pemetaan adalah set 1, ..., ndalam urutan itu. Bisakah Anda mengklarifikasi bagaimana pemetaan bisa menjadi input? Apakah ini struktur data?
Luis Mendo
@LuisMendo Ya, ini adalah struktur data, seperti Python dict. Saya ingin memiliki {1: 2, 2: 1}sebagai input, bukan [2, 1].
Tembaga

Jawaban:

12

J, 4 byte

#@C.

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.

mil
sumber
1
Itu curang! :)
orlp
1
Seharusnya saya melarang builtin :-D
Luis Mendo
2
Orang builtin adalah cinta. Orang builtin adalah kehidupan. Saya setuju itu akan lebih menyenangkan dengan bawaan yang dilarang. Jangan ragu untuk mengubah aturan sekarang juga sebelum terlalu banyak jawaban.
mil
@miles Nah, saya akan membiarkannya apa adanya. Kerja bagus!
Luis Mendo
7

JavaScript, 99 98 byte

Solusi ini mengasumsikan array dan nilainya diindeks nol (misalnya [2, 1, 0]).

f=a=>{h={},i=c=0;while(i<a.length){s=i;while(!h[i]){h[i]=1;i=a[i]}c++;i=s;while(h[++i]);}return c}

Penjelasan

// assumes the array is valid and zero-indexed
var findCycles = (array) => {
    var hash = {};  // remembers visited nodes
    var index = 0;  // current node
    var count = 0;  // number of cycles
    var start;      // starting node of cycle

    // loop until all nodes visited
    while(index < array.length) {
        start = index;  // cache starting node

        // loop until found previously visited node
        while(!hash[index]) {
            hash[index] = 1;    // mark node as visited
            index = array[index];   // get next node
        }
        count++;    // increment number of cycles

        index = start + 1;  // assume next node is right after

        // loop until found unvisited node
        while(hash[index]) {
            index++;    // get next node
        }
    }

    return count;   // return number of cycles
};
kamoroso94
sumber
3
Selamat datang di PPCG! Jawaban pertama yang bagus! Ini juga salah satu yang terbaik, jika bukan yang terbaik, jawaban pertama yang saya lihat dalam pengalaman saya! Pertahankan kerja bagus!
GamrCorps
Wow, terima kasih banyak! Saya benar-benar harus mencari cara melakukan lambda dalam JavaScript. Saya belum terbiasa dengan hal-hal ES6.
kamoroso94
6

Mathematica, 45 byte

Length@ConnectedComponents@Thread[Sort@#->#]&

Ini menghasilkan grafik dan menghitung komponen yang terhubung.

alephalpha
sumber
6

Mathematica, 37 28 27 byte

#~PermutationCycles~Length&

Terima kasih @alephalpha untuk menghemat 9 byte, dan @miles untuk 1 byte lagi.

martin
sumber
3
PermutationCycles[#,Length]&
alephalpha
3
Oh itu rapi. Saya tidak tahu PermutationCyclesbisa mengambil argumen kedua untuk mengubah kepala outputnya. Anda juga dapat menggunakan notasi infiks untuk menyimpan byte lain #~PermutationCycles~Length&.
mil
1
Juga mengenai solusi asli Anda, #&agak sedikit lebih pendek dari Identity. ;)
Martin Ender
6

Python, 77 69 67 byte

f=lambda p,i=1:i and0 **p[i-1]+f(p[:i-1]+[0]+p[i:],p[i-1]or max(p))
orlp
sumber
(not p[i-1])dapat dilakukan sebagai0**p[i-1]
xnor
5

Jelly, 12 10 9 byte

ị³$ÐĿ«/QL

Disimpan 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

ị³$ÐĿ«/QL  Input: permutation p
  $        Chain (ị³) as a monad
 ³           The input p
ị            For each value x, get the value at index x in p
   ÐĿ      Invoke it on p initially, and repeat it on its next value until it returns
           to a previous value and keep track of the results
           This will create a table where each column is the orbit of each value
     «/    Get the minimum value along each column of that table
       Q   Deduplicate
        L  Get the length and return
mil
sumber
Pendekatan yang sangat bagus!
Luis Mendo
ị³$ÐĿ«/QLharus bekerja.
Dennis
@ Dennis Wow, itu trik yang rapi! Karena setiap siklus terpisah, mengambil maksimum / menit dan menggunakannya sebagai label akan cukup untuk menduplikasi panjang + untuk hasilnya.
mil
5

Python, 64 byte

l=input()
for _ in l:l=[min(x,l[x])for x in l]
print len(set(l))

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 niterasi. Atau, kita bisa mengulanginya sampai daftar tidak lagi berubah. Strategi ini memberi saya fungsi rekursif dengan panjang yang sama, 64 byte:

f=lambda l,p=0:len(set(l*(l==p)))or f([min(x,l[x])for x in l],l)

Mengurangi adalah 65 byte

lambda l:len(set(reduce(lambda l,_:[min(x,l[x])for x in l],l,l)))

The set(_)konversi dapat dipersingkat untuk {*_}Python 3.5, menyimpan 2 bytes.

Tidak
sumber
4

Haskell, 111 byte

l!i|l!!i<0=l|1<2=(take i l++[-1]++drop(i+1)l)!(l!!i)
f(x:y)|x>=0=0|1<2=1+f y
c l|l==[-1|x<-l]=0|1<2=1+c(l!f l)

Menggunakan pengindeksan berbasis 0

Program man
sumber
4
Sial, Anda lebih baik memiliki font pemrograman yang baik :)1l!i|iIi!!1ll1|
orlp
@orlp dan 111 byte! : O
grooveplex
4

Pyth, 9 byte

l{mS.u@QN

Menggunakan indeks berbasis 0. Cobalah online .

Bagaimana itu bekerja

  m         map for d in input:
    .u        cumulative fixed-point: starting at N=d, repeatedly replace N with
      @QN       input[N]
              until a duplicate is found, and return all intermediate results
   S          sort
 {          deduplicate
l           length
Anders Kaseorg
sumber
3

JavaScript (ES6), 49 byte

a=>a.reduce(g=(c,e,i)=>e<i?g(c,a[e],i):c+=e==i,0)

Menggunakan pengindeksan berbasis nol. Penjelasan: reducedigunakan untuk memanggil fungsi bagian dalam gpada setiap elemen array. cadalah hitungan siklus, eadalah elemen array, iadalah 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.

Neil
sumber
Ketika saya menjalankan kode Anda pada array [2,1,0,3,4,5], itu crash dengan pesan ini "Ukuran stack panggilan maksimum terlampaui".
kamoroso94
1
@ kamoroso94 Maaf tentang itu, kesalahan ketik telah merayap masuk. Harus diperbaiki sekarang.
Neil
2

C, 90 byte

Panggil f()dengan intarray yang bisa berubah , 1 pengindeksan berbasis. Parameter kedua adalah ukuran array. Fungsi mengembalikan jumlah siklus.

i,j,c;f(a,n)int*a;{for(c=i=0;i<n;++i)for(j=0,c+=!!a[i];a[i];a[i]=0,i=j-1)j=a[i];return c;}

Cobalah di ideone .

Algoritma:

For each index
    If index is non-zero
        Increment counter
        Traverse the cycle, replacing each index in it with 0.
owacoder
sumber
2

GAP , 30 byte

Terus terang, argumen kedua untuk Cyclesmemberikan set di mana permutasi harus bertindak:

l->Size(Cycles(PermList(l),l))
Sievers Kristen
sumber