Tantangan
Untuk sekumpulan integer n, tulis sebuah program yang akan menampilkan indeks leksikografinya.
Aturan
- Input hanya boleh berupa satu set bilangan bulat non-negatif unik yang dipisahkan oleh spasi.
- Anda harus menampilkan indeks leksikografis (kisaran 0 hingga n! -1 inklusif) dari permutasi.
- Tidak ada perpustakaan permutasi atau permutasi bawaan yang dapat digunakan.
- Anda tidak boleh membuat set permutasi atau subset permutasi input untuk membantu Anda menemukan indeks.
- Anda juga tidak bisa menambah atau mengurangi permutasi yang diberikan ke permutasi berikutnya / sebelumnya (secara leksikografis).
- Poin bonus (-10 byte) jika Anda menemukan cara untuk menyelesaikan ini tanpa menggunakan faktorial.
- Runtime harus kurang dari 1 menit untuk n = 100
- Kode terpendek dengan jumlah byte menang
- Pemenang dipilih Selasa (22 Juli 2014)
Lebih Lanjut Tentang Permutasi
- http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
- Operasi grup permutasi
- http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html
Contohnya
0 1 2 --> 0
0 2 1 --> 1
1 0 2 --> 2
1 2 0 --> 3
2 0 1 --> 4
2 1 0 --> 5
0 1 2 3 4 5 6 7 --> 0
0 1 2 3 4 5 7 6 --> 1
0 1 2 3 4 6 5 7 --> 2
1 3 5 17 --> 0
781 780 779 13 --> 23
81 62 19 12 11 8 2 0 --> 40319
195 124 719 1 51 6 3 --> 4181
code-golf
math
combinatorics
set-theory
permutations
Kyle McCormick
sumber
sumber
Jawaban:
GolfScript, 12 (22 karakter - 10 bonus)
Poin bonus untuk tidak menggunakan faktorial. Masukan harus diberikan pada STDIN dalam format yang diuraikan dalam pertanyaan. Anda dapat mencoba kodenya secara online .
sumber
CJam, 31, dengan faktorial
sumber
Python 2 (77 = 87-10)
Bisa dibaca Banyak built-in. Wow.
Kami menggunakan fakta bahwa indeks leksikografi permutasi adalah penjumlahan dari elemen permutasi dari jumlah inversi di atas elemen tersebut (nilai setelahnya tetapi di bawahnya) dikalikan dengan faktorial dari jumlah elemen sesudahnya. Daripada mengevaluasi istilah ekspresi polinomial seperti ini dengan istilah, kami menggunakan sesuatu yang mirip dengan metode Horner .
Daripada membalik-balik indeks array, kami berulang kali menghapus elemen pertama dari daftar dan memproses elemen yang tersisa. Ekspresi
sorted(p).index(p.pop(0))
menghitung jumlah inversi yang melewati indeks pertama dengan mengambil posisinya di daftar yang diurutkan, sementara pada saat yang sama melakukan penghapusan.Sayangnya, saya harus menggunakan Python 2 dan mengambil 4 karakter lagi
raw_input
(meskipun -1 untukprint
) karena dalam Python 3map(int,...)
menghasilkan objek peta, yang tidak mendukung operasi daftar,sumber
Pyth (13 = 23-10)
Port of jawaban Python saya .
Terjemahan Python (dengan beberapa hal yang tidak relevan difilter):
Nomor input tetap string tetapi diurutkan sebagai int dengan menggunakan eval sebagai kuncinya. Daftar ini dibalik sehingga
pop
mengambil bagian depan daripada bagian belakang.sumber
Cobra - 202
Jelas Cobra tidak benar-benar bersaing dalam hal ini.
sumber
J, 5 byte (15 - 10)
Ini berjalan dalam waktu O ( n 2 ) dan dapat menangani n = 100 dengan mudah.
Pemakaian
Penjelasan
sumber