pengantar
Mari kita amati urutan berikut (bilangan bulat non-negatif):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
Sebagai contoh, mari kita ambil tiga angka pertama . Ini adalah 0, 1, 2
. Angka-angka yang digunakan dalam urutan ini dapat dipesan dalam enam cara berbeda:
012 120
021 201
102 210
Jadi, katakanlah F (3) = 6 . Contoh lain adalah F (12) . Ini berisi angka-angka:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Atau versi gabungan:
01234567891011
Untuk menemukan sejumlah cara untuk mengatur ulang ini, pertama-tama kita perlu melihat panjang string ini. Panjang string ini adalah 14
. Jadi kami menghitung 14! . Namun, misalnya yang dapat bertukar tempat tanpa mengganggu string terakhir. Ada 2 nol, jadi ada 2! cara untuk mengubah angka nol tanpa mengganggu urutannya. Ada juga 4, jadi ada 4! cara untuk beralih. Kami membagi total dengan dua angka ini:
Ada 14! / (4! × 2!) = 1816214400 cara untuk mengatur string 01234567891011
. Jadi kita dapat menyimpulkan bahwa F (12) = 1816214400 .
Tugas
Diberikan N , output F (N) . Untuk mereka yang tidak membutuhkan pengantar. Untuk menghitung F (N), pertama-tama kita menggabungkan bilangan bulat N-negatif pertama (misalnya untuk N = 12, string yang digabungkan akan menjadi 01234567891011
) dan menghitung jumlah cara untuk mengatur string ini.
Uji kasus
Input: Output:
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 119750400
12 1816214400
13 43589145600
14 1111523212800
15 30169915776000
Catatan
Menghitung jawaban harus dihitung dalam batas waktu 10 detik , brute-force tidak diperbolehkan .
Ini adalah kode-golf , jadi pengiriman dengan jumlah byte paling sedikit menang!
10
benar? Rasanya seperti itu harus kurang dari 10 !, karena di situlah angka yang berulang dimulai.10
Digit pertama adalah0, 1, 2, 3, 4, 5, 6, 7, 8, 9
. Sepuluh digit berbeda, jadi hasilnya 10!0
kasus ini melempar hitungan saya (string kosong bodoh).F(N)
tidakO(N!)
dan itulog F(N)
adalahO(log N!)
tetapi mereka hanya firasat ...Jawaban:
Jelly,
1715 byteCobalah online! atau verifikasi semua kasus uji sekaligus .
Bagaimana itu bekerja
sumber
ES6,
1188178 byteSeseorang pasti memberi tahu saya bahwa ada cara yang lebih singkat untuk merangkai angka-angka itu
n
.Menyimpan 37 byte keren dengan mengambil ide @ edc65 dan menjalankannya dengan steroid. (Simpan byte tambahan dengan menggunakan '|' alih-alih
&&
tetapi itu membatasi hasilnya hingga 31 bit.)Sunting: Disimpan 3 byte lebih lanjut lagi berkat @ edc65.
sumber
reduce
:n=>[...[...Array(n).keys()].join``].reduce((r,c,i)=>r*++i/(o[c]=-~o[c]),1,o=[])
n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r
r/=(...)/i++
lebih akurat daripadar*=i++/(...)
? Itu golf paling menggelikan yang pernah saya lihat!APL (Dyalog Extended) , 13 byte
Cobalah online!
Program lengkap. Penggunaan
⎕IO←0
.Bagaimana itu bekerja
Perhitungan multinomial berasal dari fakta berikut:
sumber
MATL , 21 byte
Cobalah online!
Penjelasan
sumber
Python 2,
14213710197 byte(Terima kasih @adnan untuk sarannya
input
)(Diterapkan perhitungan inkremental dari versi C )
Versi asli menggunakan faktorial
Sungguh, satu-satunya golf di atas adalah panggilan
math.factorial
F
dan meninggalkan beberapa ruang, jadi mungkin ada solusi python yang lebih pendek.Jika diperlukan penjelasan,
v
pertahankan hitungan frekuensi setiap digit; hitungan diperbarui untuk setiap digit di setiap angka dalam rentang yang ditunjukkan.Dalam versi asli, kami menghitung jumlah permutasi menggunakan rumus standar (Σf i )! / Π (f i !). Untuk versi saat ini, perhitungan ini dilakukan secara bertahap dengan mendistribusikan multiplies dan membagi seperti yang kita lihat digit. Mungkin tidak jelas bahwa pembagian bilangan bulat akan selalu tepat, tetapi mudah untuk membuktikan berdasarkan pengamatan bahwa setiap divisi
k
harus mengikutik
multiplies dari integer berturutan, sehingga salah satu dari multiplies tersebut harus dapat dibagi olehk
. (Itu intuisi, bukan bukti.)Versi asli lebih cepat untuk argumen besar karena hanya membagi 10 bignum. Meskipun membagi bignum dengan bilangan bulat kecil lebih cepat daripada membagi bignum dengan bignum, ketika Anda memiliki ribuan bignum membagi, itu menjadi sedikit lamban.
sumber
Python 2, 197 Bytes (sunting: disimpan 4 byte, terima kasih Thomas Kwa!)
Tidak Disatukan:
sumber
range(0,10)
bisarange(10)
.CJam,
2119 byteUji di sini.
Penjelasan
sumber
JavaScript (ES6), 100
Uji
sumber
k[c]=~-k[c]
identik dengan--k[c]
?Pyth, 18 byte
Cobalah online: Demonstrasi
sumber
Haskell, 92 byte
Contoh penggunaan:
h 12
->1816214400
.Bagaimana itu bekerja
sumber
C,
236174138121 byteBanyak kredit untuk rici, untuk pengurangan besar byte.
Tidak disatukan
Coba di sini .
sumber
#define L long long L d;i,j,k,m,n,s=1,b[10]={1};L f(n){return n?n*f(n-1):1;}main(d){for(scanf("%d",&n);i<n;)for(j=i++;j;j/=10)++b[j%10],++s;for(;m<10;)d*=f(b[m++]);printf("%Ld",f(s)/d);}
for(;m<10;)s+=b[m],d*=f(b[m++])
tapi saya pikir itu beberapa byte lagi.C / bc,
233121112 byte (dengan asumsi penalti 3 byte untuk|bc
)Terinspirasi oleh Cole Cameron, menghapus manipulasi karakter hacky dan hanya melakukan aritmatika pada nilai argumen.
Berubah menjadi scanf dari menggunakan arg arg.
Perlu
bc
benar-benar melakukan perhitungan presisi yang sewenang-wenang.Tidak disatukan dan bebas peringatan:
Diilustrasikan (yang saya percayai menunjukkan algoritme):
Dan, dengan pipa melalui bc (dan menambahkan perhitungan F (1000):
Ini menghitung F (5000) - angka 18.592 digit - dalam waktu kurang dari 10 detik.
sumber
Perl 6, 117 byte
dan dalam fasion yang lebih mudah dibaca
sumber
Perl 5, 108 byte
Banyak terima kasih kepada dev-null karena telah menyelamatkan saya 17 byte, dan untuk japhy atas ide faktorial.
sumber
05AB1E ,
131211 byteCobalah online!
sumber
Python 2 , 123 byte
Cobalah online!
range
input menjadi string tunggalsumber
PowerShell, 125 byte
Mengambil input
$args[0]
, mengurangi1
, membangun serangkaian bilangan bulat dari0..
angka itu,-join
menyatukannya menjadi sebuah string, dan menyimpannya sebagai$b
. Kami mengambil.Length
string itu, membangun rentang lain dari1..
panjang itu,-join
bilangan bulat itu bersama*
, lalu menyalurkannya keInvoke-Expression
(mirip denganeval
). Dengan kata lain, kami telah membangun faktorial dari panjang urutan nomor berdasarkan input. Itu pembilang kita.Kami membaginya
/
dengan ...Penyebut kami, yang dibangun dengan mengambil jarak
0..9
dan mengirimkannya melalui for-loop|%{...}
. Setiap iterasi, kami menetapkan variabel pembantu$c
sama dengan berapa kali digit saat ini$_
muncul dalam$b
berkat panggilan NET[regex]::matches
ditambah dengan.count
atribut. Kami kemudian membuat rentang baru dari1..
hingga nilai itu, asalkan bukan nol. Ya, dalam banyak kasus, ini akan menghasilkan kisaran1..1
, yang dievaluasi menjadi adil1
. Kami mengambil semua itu dan-join
mereka bersama-sama*
, lalu menyambungkannyaInvoke-Expression
lagi. Dengan kata lain, kami telah membuat produk faktorial dari jumlah kemunculan setiap digit.NB
Menangani input hingga
90
tanpa masalah dan secara signifikan kurang dari satu detik.... di luar itu menghasilkan
Infinity
sebagai output, karena panjang string yang diijinkan menghasilkan170!
cocok dengandouble
tipe data (7.25741561530799E+306
), tetapi171!
tidak. PowerShell memiliki ... permainan kata-kata ... yang secara otomatis up-gips dari[int]
ke[double]
dalam kasus overflow (asalkan Anda tidak secara eksplisit melemparkan variabel untuk memulai dengan). Tidak, saya tidak tahu mengapa itu tidak menggunakan[long]
nilai integer.Jika kami melakukan beberapa casting dan manipulasi eksplisit (misalnya, menggunakan
[uint64]
, untuk integer 64-bit yang tidak ditandatangani), kami bisa mendapatkan yang lebih tinggi, tetapi itu akan menggembungkan kode secara signifikan karena kami perlu berkisar hingga 170-panjang dengan kondisional dan kemudian menyusun kembali setiap perkalian dari sana ke depan. Karena tantangannya tidak menentukan kisaran atas, saya menganggap ini sudah memadai.sumber
Perl6
Agak ungolfed saat ini - perlu tidur sekarang.
sumber
Groovy, 156 byte
Solusi Code Golf pertama saya yang sederhana. Anda bisa mengujinya di sini.
Dan ini versi yang lebih mudah dibaca:
Cukup mudah, tetapi ada beberapa highlight untuk saya:
Melakukan suntikan / pengurangan dari array
chars
keMap<Character, Integer>
. Ini masih sedikit rumit oleh kurangnya nilai default untuk nilai peta. Keraguan ini mungkin, tetapi jika peta men-default semua nilai ke 0, saya bisa menghindari ternary yang diperlukan untuk menghindari NPE.Operator penyebaran Groovy (mis.
}*.value
) Selalu menyenangkan untuk digunakanPada fitur yang mengganggu, adalah keharusan untuk mendeklarasikan fungsi faktorial dengan tipe kembali
BigInteger
. Saya mendapat kesan bahwa Groovy membungkus semua angkaBigInteger
atauBigDecimal
, tetapi ini mungkin tidak terjadi ketika datang untuk mengembalikan tipe. Saya harus bereksperimen lebih banyak. Tanpa jenis pengembalian ini secara eksplisit dinyatakan, kami mendapatkan nilai faktorial yang salah dengan sangat cepat.sumber
J, 33 byte
Ubah rentang menjadi string digit, hitung setiap digit, dan terapkan koefisien multinomial untuk menghitung hasilnya.
Pemakaian
sumber
R, 118 byte
Sekitar 8 bulan terlambat ke pesta tetapi berpikir saya akan mencobanya karena itu tampak seperti tantangan yang menarik.
Cobalah R-biola
Dijelaskan
0 ... n-1
dan runtuh ke string:paste(1:n-1,collapse="")
x
):x=as.numeric(el(strsplit(...,"")))
factorial(sum(1|x))
mana saja#digits!
Untuk menghitung penyebut kita menggunakan
table
untuk membangun tabel kontingensi yang berisi daftar frekuensi. Dalam kasus F (12) tabel yang dihasilkan adalah:Yang berarti kita dapat menggunakan
factorial()
(yang by the vectorized) menggunakan hitungan dan hanya mengambil produk:prod(factorial(table(x)))
Catatan: langkah 4 dan 5 hanya dijalankan jika
n>0
sebaliknya kembali1
.sumber
Mathematica, 65 byte
Mungkin bisa bermain golf lebih lanjut.
sumber
Ruby , 64 byte
Cobalah online!
sumber
Stax , 12 byte
Jalankan dan debug di staxlang.xyz!
Dibongkar (14 byte) dan penjelasan:
sumber
Jelly , 11 byte
Golfed 15 byte Jelly menjawab ...
Tautan monadik yang menerima bilangan bulat non-negatif yang menghasilkan bilangan bulat positif.
Cobalah online! Atau lihat suite tes .
Bagaimana?
sumber
Python 2 , 190 byte
Cobalah online!
sumber
Python 2 , 134 byte
Cobalah online!
Pendekatan alternatif ...
sumber