pengantar
Misalkan Anda diberikan permutasi n
objek secara acak . Permutasi disegel dalam sebuah kotak, jadi Anda tidak tahu yang mana dari n!
kemungkinan itu. Jika Anda berhasil menerapkan permutasi ke n
objek yang berbeda, Anda dapat langsung menyimpulkan identitasnya. Namun, Anda hanya diizinkan untuk menerapkan permutasi ke n
vektor biner panjang, yang berarti Anda harus menerapkannya beberapa kali untuk mengenalinya. Jelas, menerapkannya ke n
vektor dengan hanya satu yang 1
melakukan pekerjaan, tetapi jika Anda pintar, Anda dapat melakukannya dengan log(n)
aplikasi. Kode untuk metode itu akan lebih panjang, meskipun ...
Ini adalah tantangan eksperimental di mana skor Anda merupakan kombinasi dari panjang kode dan kompleksitas kueri , yang berarti jumlah panggilan ke prosedur bantu. Speknya agak panjang, jadi tahan dengan saya.
Tugas
Tugas Anda adalah menulis fungsi bernama (atau setara terdekat) f
yang mengambil input bilangan bulat positif n
, dan permutasi bilangan bulat p
pertama n
, menggunakan pengindeksan berbasis 0 atau 1 berbasis. Outputnya adalah permutasi p
. Namun, Anda tidak diizinkan mengakses permutasi p
secara langsung . Satu-satunya hal yang dapat Anda lakukan dengannya adalah menerapkannya pada vektor n
bit apa pun . Untuk tujuan ini, Anda harus menggunakan fungsi bantu P
yang mengambil permutasi p
dan vektor bit v
, dan mengembalikan vektor permutasi yang p[i]
koordinatnya berisi bit v[i]
. Sebagai contoh:
P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]
Anda dapat mengganti "bit" dengan dua nilai berbeda, seperti 3
dan -4
, atau 'a'
dan 'b'
, dan mereka tidak perlu diperbaiki, sehingga Anda dapat memanggil P
keduanya [-4,3,3,-4]
dan [2,2,2,1]
panggilan yang sama f
. Definisi P
tidak dihitung terhadap skor Anda.
Mencetak gol
The kompleksitas permintaan dari solusi Anda pada masukan yang diberikan adalah jumlah panggilan itu membuat untuk fungsi tambahan P
. Agar ukuran ini tidak ambigu, solusi Anda harus deterministik. Anda dapat menggunakan angka pseudo-acak, tetapi kemudian Anda juga harus memperbaiki seed awal untuk generator.
Dalam repositori ini Anda akan menemukan file bernama permutations.txt
yang berisi 505 permutasi, 5 masing-masing panjang antara 50 dan 150 inklusif, menggunakan pengindeksan berbasis 0 (menambah setiap angka dalam kasus berbasis 1). Setiap permutasi berada pada barisnya sendiri, dan jumlahnya dipisahkan oleh spasi. Skor Anda adalah jumlah byte f
+ kompleksitas kueri rata-rata pada input ini . Skor terendah menang.
Aturan Ekstra
Kode dengan penjelasan lebih disukai, dan celah standar tidak diizinkan. Secara khusus, bit individual tidak dapat dibedakan (sehingga Anda tidak dapat memberikan vektor Integer
objek ke P
dan membandingkan identitas mereka), dan fungsi P
selalu mengembalikan vektor baru alih-alih mengatur inputnya. Anda dapat dengan bebas mengubah nama f
dan P
, dan urutan pengambilan argumen mereka.
Jika Anda adalah orang pertama yang menjawab dalam bahasa pemrograman Anda, Anda sangat dianjurkan untuk memasukkan test harness, termasuk implementasi fungsi P
yang juga menghitung berapa kali dipanggil. Sebagai contoh, inilah harness untuk Python 3.
def f(n,p):
pass # Your submission goes here
num_calls = 0
def P(permutation, bit_vector):
global num_calls
num_calls += 1
permuted_vector = [0]*len(bit_vector)
for i in range(len(bit_vector)):
permuted_vector[permutation[i]] = bit_vector[i]
return permuted_vector
num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
num_lines += 1
perm = [int(n) for n in line.split()]
guess = f(len(perm), perm)
if guess != perm:
print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
break
else:
print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()
Dalam beberapa bahasa, tidak mungkin menulis harness seperti itu. Terutama, Haskell tidak mengizinkan fungsi murni P
untuk mencatat berapa kali dipanggil. Karena alasan ini, Anda diizinkan untuk mengimplementasikan kembali solusi Anda sedemikian rupa sehingga ia juga menghitung kompleksitas kuerinya, dan menggunakannya dalam harness.
abaaabababaa
dan-4 3 3 3 -4 3
akan menjadi vektor bit.Jawaban:
J,
44.069322.0693 =3715 + 7.06931Jika kita tidak dapat memanggil
P
padai. n
, setidaknya kita bisa panggilanP
pada setiap biti. n
secara terpisah. Jumlah doaP
adalah>. 2 ^. n
(⌈log 2 n ⌉). Saya percaya ini optimal.Berikut ini adalah implementasi dari fungsi
P
yang menggunakan vektor permutasip
dan menyimpan jumlah doaPinv
.Berikut ini adalah harness pengujian yang menerima permutasi dan mengembalikan jumlah pemanggilan
p
:Dan di sini adalah bagaimana Anda dapat menggunakannya di file
permutations.txt
:Penjelasan
Penjelasan singkat sudah disediakan di atas, tetapi di sini ada yang lebih rinci. Pertama,
f
dengan spasi yang disisipkan dan sebagai fungsi eksplisit:Baca:
di mana y adalah parameter formal ke f. dalam J, parameter ke (fungsi) disebut x dan y jika kata kerjanya adalah diad (memiliki dua parameter) dan y jika itu monadic (memiliki satu parameter).
Alih-alih meminta
P
padai. n
(yaitu0 1 2 ... (n - 1)
), kami memintaP
pada setiap posisi bit dari angka dii. n
. Karena semua permutasi melakukan permutasi dengan cara yang sama, kita dapat menyusun kembali bit-bit permutasi menjadi angka-angka untuk mendapatkan vektor permutasi:i. y
- bilangan bulat dari0
key - 1
.#: y
-y
diwakili dalam basis 2. Ini diperluas ke vektor angka dengan cara alami. Misalnya,#: i. 16
hasil:#. y
-y
ditafsirkan sebagai nomor basis 2. Khususnya, ini kebalikan dari#:
;y ~: #. #:
selalu berlaku.|: y
-y
dipindahkan.u&.v y
-u
bawahv
, divinv u v y
situlahvinv
kebalikannyav
. Perhatikan bahwa itu|:
adalah kebalikannya sendiri.P y
- fungsi yangP
diterapkan untuk setiap vektory
menurut definisi.sumber
Pyth 32 + 7.06931 = 37.06931
Saya menemukan algoritma berikut ini sepenuhnya independen. Tapi ini kurang lebih sama dengan solusi J FUZxxl yang sangat singkat (sejauh yang saya mengerti).
Pertama definisi fungsi
P
, yang memungkinkan bit-array sesuai dengan permutasi yang tidak diketahui.Dan kemudian kode, yang menentukan permutasi.
Ini mendefinisikan fungsi
g
, yang membutuhkan dua argumen. Anda dapat memanggilnya dengang5[4 2 1 3 0
. Ini demonstrasi online . Tidak pernah menggunakan begitu banyak (5) peta bersarang.Tapi saya belum benar-benar membuat test harness. Fungsi itu tidak
P
menghitung berapa kali saya menyebutnya. Saya telah menghabiskan banyak waktu untuk mencari tahu algoritma. Tetapi jika Anda membaca penjelasan saya, cukup jelas bahwa itu menggunakanint(log2(n-1)) + 1
panggilan (= ceil(log2(n))
). Dansum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069
.Penjelasan:
Saya sebenarnya kesulitan menemukan algoritma ini. Tidak jelas bagi saya sama sekali, bagaimana mencapainya
log(n)
. Jadi saya mulai melakukan beberapa percobaan dengan yang keciln
.Catatan pertama: Bit-array mengumpulkan informasi yang sama dengan bit-array. Oleh karena itu semua bit-array dalam solusi saya memiliki
n/2
bit paling aktif.n = 3:
Karena kita hanya dapat menggunakan bit-array dengan 1 bit aktif, solusi optimal tergantung pada dua panggilan. Misalnya
P([1, 0, 0])
danP([0, 1, 0])
. Hasilnya memberitahu kita jumlah permutasi pertama dan kedua, secara tidak langsung kita mendapatkan yang ketiga.n = 4:
Ini dia sedikit menarik. Kita sekarang dapat menggunakan dua jenis bit-array. Yang dengan 1 bit aktif dan yang dengan 2 bit aktif. Jika kami menggunakan bit-array dengan satu bit aktif, kami hanya mengumpulkan informasi tentang satu nomor permutasi, dan kembali ke
n = 3
, menghasilkan1 + 2 = 3
panggilanP
. Bagian yang menarik adalah kita dapat melakukan hal yang sama dengan hanya 2 panggilan, jika kita menggunakan bit-array dengan 2 bit aktif. MisalnyaP([1, 1, 0, 0])
danP([1, 0, 1, 0])
.Katakanlah kita mendapatkan output
[1, 0, 0, 1]
dan[0, 0, 1, 1]
. Kita lihat, bahwa bit nomor 4 aktif di kedua array output. Satu-satunya bit yang aktif di kedua array input adalah bit nomor 1, jadi jelas permutasi dimulai dengan4
. Sekarang mudah untuk melihat, bahwa bit 2 dipindahkan ke bit 1 (output pertama), dan bit 3 dipindahkan ke bit 3 (output kedua). Oleh karena itu permutasi harus[4, 1, 3, 2]
.n = 7:
Sekarang sesuatu yang lebih besar. Saya akan segera menunjukkan panggilan
P
. Mereka adalah satu kali, yang saya buat setelah sedikit berpikir dan bereksperimen. (Perhatikan ini bukan yang saya gunakan dalam kode saya.)Jika dalam dua array output pertama (dan bukan yang ketiga) bit 2 aktif, kita tahu bahwa permutasi bergerak bit 1 ke bit 2, karena bit satu adalah satu-satunya bit yang aktif dalam dua array input pertama.
Yang penting adalah, bahwa (menafsirkan input sebagai matriks) masing-masing kolom adalah unik. Ini mengingatkan saya pada kode Hamming , di mana hal yang sama tercapai. Mereka hanya mengambil angka 1 hingga 7, dan menggunakan representasi bit mereka sebagai kolom. Saya akan menggunakan angka 0 hingga 6. Sekarang bagian yang bagus, kita dapat mengartikan output (lagi kolom) sebagai angka lagi. Ini memberi tahu kami hasil dari permutasi yang diterapkan
[0, 1, 2, 3, 4, 5, 6]
.Jadi kita hanya perlu melacak kembali angka-angkanya. Bit 0 berakhir di bit 5, bit 1 berakhir di bit 0, bit 2 berakhir di bit 6, ... Jadi permutasi adalah
[5, 0, 6, 1, 3, 4, 2]
.Dan kode untuk fungsi permutasi:
sumber
*sltQ]0
denganm0sltQ
, Anda bisa memiliki 6 peta bersarang dengan panjang yang sama.f
meskipun nama lain diizinkan. Tugas ini diperhitungkan terhadap skor Anda.g
alih-alih membaca dari STDIN.Mathematica, 63 + 100 = 163
Saya menggunakan permutasi berbasis satu, karena itulah cara pengindeksan bekerja di Mathematica.
Pertama, test harness. Ini adalah fungsi kueri
p
(nama yang ditentukan pengguna tidak boleh menggunakan huruf besar di Mathematica):Dan persiapan input bersama dengan loop tes:
Dan akhirnya, kiriman saya yang sebenarnya yang menggunakan algoritma naif untuk saat ini:
Atau dengan lekukan:
sumber