pengantar
Permutasi leksikografis dari daftar dengan elemen n dapat dinomori dari 0 hingga n ! - 1. Misalnya, 3! = 6 permutasi dari (1,2,3)
akan (1,2,3)
, (1,3,2)
, (2,1,3)
, (2,3,1)
, (3,1,2)
, (3,2,1)
.
Ketika permutasi diterapkan ke daftar, elemen-elemennya disusun dalam urutan yang sama dengan angka dalam permutasi. Sebagai contoh, menerapkan permutasi (2,3,1)
ke l = (a,b,c)
hasil (l[2],l[3],l[1]) = (b,c,a)
.
Kebalikan dari permutasi didefinisikan sebagai permutasi yang membalikkan operasi ini, yaitu menerapkan permutasi dan kemudian kebalikannya (atau sebaliknya) tidak mengubah array. Misalnya, kebalikannya (2,3,1)
adalah (3,1,2)
, sejak menerapkannya pada (b,c,a)
hasil (a,b,c)
.
Juga, kebalikan permutasi yang diterapkan pada permutasi itu sendiri menghasilkan bilangan bulat 1 ... n . Misalnya, menerapkan (3,1,2)
untuk (2,3,1)
hasil (1,2,3)
.
Kami sekarang mendefinisikan fungsi revind ( x ) sebagai indeks permutasi terbalik dari permutasi dengan indeks x . (Ini A056019 , jika Anda tertarik.)
Karena permutasi dengan indeks saya hanya memodifikasi item k terakhir dari daftar iff 0 ≤ i < k !, kita dapat menambahkan sejumlah elemen ke awal daftar tanpa mempengaruhi revind ( i ). Oleh karena itu panjang daftar tidak mempengaruhi hasilnya.
Tantangan
Tugas Anda adalah mengimplementasikan revind ( x ). Anda akan menulis program atau fungsi lengkap yang menggunakan satu integer nonnegatif x sebagai input / argumen dan menghasilkan / mengembalikan hasilnya sebagai integer nonnegatif tunggal.
Input dan output mungkin 0-diindeks atau 1-diindeks, tetapi ini harus konsisten di antara mereka.
Bawaan yang menghasilkan permutasi dengan indeks, mengembalikan indeks permutasi atau menemukan permutasi terbalik dilarang. (Builtin yang menghasilkan semua permutasi atau permutasi berikutnya diizinkan.)
Aturan standar kode-golf berlaku.
Contohnya
Contoh di bawah ini adalah 0-diindeks.
Input Output
0 0
1 1
2 2
3 4
4 3
5 5
6 6
13 10
42 51
100 41
1000 3628
2000 3974
10000 30593
100000 303016
Implementasi referensi (Python 3)
def revind(n):
from math import factorial
from itertools import permutations, count
l = next(filter(lambda x: factorial(x) > n, count(1)))
pms = list(permutations(range(l)))
return [k for k in range(len(pms)) if tuple(pms[n][i] for i in pms[k]) == pms[0]][0]
sumber
(a,b,c)
sangat tidak jelas. Harap sertakan penjelasan yang tepat tentang apakah permutasi terbalik itu.Ụ
(tingkat atas) yang mengurutkan indeks array dengan nilai yang sesuai. Ini terjadi untuk membalikkan permutasi 1, ..., n , tetapi itu tidak berfungsi untuk permutasi lainnya. ApakahỤ
built-in terlarang?Jawaban:
Jeli , 6 byte
I / O menggunakan pengindeksan berbasis 1. Sangat lambat dan haus akan memori.
Verifikasi
Selama input tidak melebihi 8! = 40320 , itu sudah cukup untuk mempertimbangkan semua permutasi dari array [1,…, 8] . Untuk kasus uji terakhir, permutasi [1,…, 9] sudah cukup.
Dengan kode yang sedikit dimodifikasi yang hanya mempertimbangkan permutasi dari 8 atau 9 bilangan bulat positif pertama, Anda dapat mencobanya secara online! atau verifikasi semua kasus uji yang tersisa .
Bagaimana itu bekerja
Pendekatan alternatif, 6 byte (tidak valid)
Itu sama panjang dan menggunakan tingkat terlarang naik atom
Ụ
, tapi itu (bisa dibilang) lebih idiomatis.Dengan mengawali 8 (atau 9 untuk test case terakhir), kita dapat mencobanya secara online!
Bagaimana itu bekerja
sumber
Mathematica, 74 byte
Menggunakan pengindeksan 1. Sangat tidak efisien. (menggunakan ~ 11GB memori saat inputnya
11
)Penjelasan
Buat daftar dari 1 hingga N. Simpan di
j
.Temukan semua permutasi dari
j
. Simpan itu dii
.Simpan
Position
fungsi dik
. (untuk mengurangi byte-count saat menggunakanPosition
lagi)Temukan permutasi kebalikan dari permutasi ke-N.
Temukan
k
(Position
) dari permutasi terbalik dii
(semua permutasi)Menggunakan built-in,
4643 byte1-diindeks.
sumber
MATL , 15 byte
Input dan output berbasis 1.
Mirip dengan jawaban CJam @ MartinEnder , tetapi menemukan permutasi terbalik dengan menyusun semua permutasi yang mungkin dengan yang ditentukan oleh input, dan melihat yang telah menjadi permutasi identitas.
Kehabisan memori dalam kompiler online untuk input
10
.Cobalah online!
Penjelasan
sumber
Pyth, 12 byte
Suite uji
0 diindeks.
Penjelasan:
sumber
05AB1E ,
1413 byteMemori sangat tidak efisien.Sekarang bahkan lebih banyak memori tidak efisien (tetapi lebih pendek 1 byte).Kisaran berbasis 0.
Menggunakan pengodean CP-1252 .
Cobalah online! atau sebagai test suite yang dimodifikasi
Penjelasan
sumber
CJam , 16 byte
Indeks berbasis 0.
Cobalah online!
Saya tidak mendapatkan jauh lebih tidak efisien daripada ini ... kehabisan memori dengan pengaturan default Java untuk input lebih besar dari
8
(tetapi bekerja pada prinsipnya untuk input sewenang-wenang diberikan jumlah yang cukup dari semesta waktu dan memori).Penjelasan
sumber
GAP , 108 byte
1-diindeks. Baris baru tidak dihitung, tidak diperlukan. Saya tidak benar-benar harus menetapkan fungsi akhir ke sebuah nama, tapi ...
h
adalah fungsi kari mengambil daftar permutasi dan indeks ke dalam daftar itu dan mengembalikan indeks permuasi terbalik. Tanpa batasan, saya hanya akan melakukannyaPosition(l,l[n]^-1)
.f
memanggil fungsi itu dengan permutasi yang diurutkan dari grup simetris yang cukup besar dan diberikann
.Saya hanya bisa menulis
SymmetricGroup(n)
, lalu fungsinya dapat dihitung untuk nilai hingga 9. Karena sudah ada solusi yang jauh lebih kecil, saya lebih suka untuk dapat melakukan ini:Solusi terindeks 0 yang sangat efisien yang berfungsi untuk argumen di bawah 99! (dan dapat digunakan untuk argumen di bawah 999! dengan biaya satu byte) adalah yang ini:
Setelah menghapus spasi putih, ini memiliki 255 byte.
sumber
JavaScript (ES6),
163120110 byteDiindeks 0. Bekerja dengan mengonversi indeks ke permutasi, membalikkannya, lalu mengonversi kembali ke indeks. Sunting: Disimpan sekitar 25% dengan membuat
f
pembalikan dan membalikkan permutasi, kemudian membuatg
mengubah permutasi terbalik menjadi indeks. Menyimpan 10 byte lebih lanjut dengan menggabungkan dua panggilan rekursif menjadi satu fungsi. Tidak Disatukan:sumber
f
membalikkan permutasi bukannyag
...J,
5550 byteBerdasarkan esai J pada Indeks Permutasi .
Kode ini hanya membutuhkan memori sesuai urutan
n
tetapi menggunakan lebih banyak waktu karena kode ini mengurutkan waktu daftarn
dan mencarin
waktu itu untuk setiap indeks.Menggunakan builtin
/:
yang dapat menemukan tingkat daftar dan kebalikan dari permutasi, ada solusi 42 byte yang lebih efisien.Versi ini hanya membutuhkan 44 detik untuk menghitung test case terakhir jika dibandingkan dengan yang lainnya yang membutuhkan 105 detik.
Pemakaian
sumber
Jelly ,
14 139 byte-4 byte terima kasih kepada @Dennis (yang dia mainkan lebih jauh menggunakan quick
⁺
dalam jawabannya )Implementasi lain yang sangat lambat.
Pengindeksan berbasis 1 digunakan di sini, jadi hasil yang diharapkan adalah:
Tidak ada gunanya bahkan memasang tautan IDE online, karena TIO membunuh pada input
10
. Hasil lokal (terakhir sangat lambat dan membutuhkan satu ton memori!):Bagaimana?
Catatan: tidak perlu mengurutkan permutasi karena kami menggunakan urutan yang sama untuk menemukan permutasi dan dan itu terbalik.
sumber
ÇịịÇ$iR
?R
sebelumnyaŒ!
adalah implisit, jadiŒ!ịịŒ!$iR
harus melakukan pekerjaan.Python 2,
116114 byterepl.it
Berbasis 0. Lambat dan memori haus tetapi kekurangan byte.
Tidak menggunakan fungsi permutasi; baik memori dan waktu efisien.
289285 byte-4 byte terima kasih kepada @Christian Sievers (permutasi penuh sudah terbentuk)
Saya tahu ini kode golf tetapi saya pikir @ Pietu1998 tertarik pada implementasi yang efisien juga.
Lihat beraksi di repl.it
Meskipun ini menggunakan lebih banyak byte daripada perbandingan implementasi referensi untuk
n=5000000
:f
adalah fungsi indeks terbalik.f
pertama mendapatkan faktorial berikutnya di atasn
,,t
dan bilangan bulat yang faktorialnya adalah,x
dengan memanggilh(n)
, dan setg=range(x)
, item yang akan membentuk permutasi,o=g[:]
,, dan pemegang permutasi,r=[]
Selanjutnya itu membangun permutasi pada indeks
n
denganpop
memasukkan indeks dari representasi basis faktorialn
pada gilirannya dari itemo
,, dan menambahkannyar
. Representasi dasar faktorial ditemukan oleh div dan modn
dengan dit
manat
div'd olehx
danx
turun ke1
.Akhirnya ia menemukan indeks permutasi terbalik dengan memanggil
i
dengan permutasi terbalik,[r.index(v)for v in g]
h
adalah fungsi tujuan ganda untuk menghitung faktorial dari bilangan non-negatif atau menghitung faktorial berikutnya di atas bilangan non-negatif dan bilangan bulat yang membuat faktorial itu.Dalam keadaan default
v=1
dan melakukan yang terakhir dengan mengalikanv
denganx
(juga awalnya1
) dan menambahx
sampain
setidaknya sama besar, lalu kembaliv
danx-1
dalam tupel.Untuk menghitung
n!
satu panggilanh(n,0)
yang kelipatanx
(awalnya1
) olehn
dan decrementsn
sampain
adalah0
ketika pengembalianx
.i
memberikan indeks leksikografis permutasi,,p
dari item[0,1,...n]
dengan menjumlahkan produk faktorial dari basis faktorial setiap indeksh(len(p)-j-1,0)
,, dan berapa banyak item di sebelah kanan indeks kurang dari nilai pada indeks itusum(k<p[j]for k in p[j+1:])
,.sumber
t/=x
.(r+o)
denganr
.Python 2,
130129 bytesumber
Sebenarnya ,
1811 byteJawaban ini menggunakan algoritme dalam jawaban Dennis 'Jelly tetapi diindeks 0. Selamat datang saran bermain golf! Cobalah online!
Tidak melakukanolf
sumber