Deranged! Combinatorics: Hitung Subfaktorial

25

Angka subfaktorial atau rencontres ( A000166 ) adalah urutan angka yang mirip dengan angka faktorial yang muncul dalam kombinatorik permutasi. Khususnya n th subfactorial ! N memberikan jumlah derangements dari satu set n elemen. Gangguan adalah permutasi di mana tidak ada elemen yang tersisa di posisi yang sama. Subfaktorial dapat didefinisikan melalui relasi rekurensi berikut:

!n = (n-1) (!(n-1) + !(n-2))

Faktanya, relasi perulangan yang sama berlaku untuk faktorial, tetapi untuk subfaktorial kita mulai dari:

!0 = 1
!1 = 0

(Untuk faktorial yang kita miliki, tentu saja, 1! = 1. )

Tugas Anda adalah menghitung ! N , diberikan n .

Aturan

Seperti faktorial, subfaktorial tumbuh dengan sangat cepat. Tidak apa-apa jika program Anda hanya dapat menangani input dan sedemikian rupa sehingga ! N dapat diwakili oleh tipe nomor asli bahasa Anda. Namun, algoritma Anda harus secara teori berfungsi untuk arbitrary n . Itu berarti, Anda dapat mengasumsikan bahwa hasil integral dan nilai menengah dapat diwakili dengan tepat oleh bahasa Anda. Perhatikan bahwa ini tidak termasuk konstanta e jika disimpan atau dihitung dengan presisi terbatas.

Hasilnya perlu bilangan bulat yang tepat (khususnya, Anda tidak dapat memperkirakan hasilnya dengan notasi ilmiah).

Anda dapat menulis sebuah program atau fungsi dan menggunakan salah satu metode standar untuk menerima input dan memberikan output.

Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.

Ini adalah , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.

Uji Kasus

n     !n
0     1
1     0
2     1
3     2
4     9
5     44
6     265
10    1334961
12    176214841
13    2290792932
14    32071101049
20    895014631192902121
21    18795307255050944540
100   34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601
Martin Ender
sumber
Terkait
Martin Ender

Jawaban:

19

Funciton , 336 byte

Hitungan byte mengasumsikan pengodean UTF-16 dengan BOM.

┌─╖┌─╖  ┌─╖ 
│f╟┤♭╟┐┌┤♭╟┐
╘╤╝╘═╝├┘╘═╝├────┐
 │┌─╖ │ ┌┐┌┘╔═╗╓┴╖
 ││f╟─┴┐└┴┼─╢0║║f║
 │╘╤╝  │  │ ╚═╝╙─╜
 │┌┴╖ ┌┴╖┌┴╖ ╔═╗
 ││+╟┐│×╟┤?╟┐║1║
 │╘╤╝│╘╤╝╘╤╝┘╚╤╝
 └─┘ └─┘  └───┘

Ini mendefinisikan fungsi fyang mengambil satu bilangan bulat dan mengeluarkan bilangan bulat lainnya pada belokan 90 derajat ke kiri. Ini bekerja untuk input besar yang sewenang-wenang.

Cobalah online!

Mengingat ini adalah Funciton, itu bahkan cukup cepat (n = 20 membutuhkan sekitar 14 detik pada TIO). Perlambatan utama datang dari rekursi ganda, karena saya tidak berpikir penerjemah Funciton secara otomatis memo fungsi.

Sayangnya, beberapa font monospasi tidak dengan benar monospace dan / atau menyisipkan celah kecil di antara garis. Berikut screenshot dari kode dari TIO dengan segala keindahannya:

masukkan deskripsi gambar di sini

Saya pikir mungkin untuk golf ini lagi, misalnya dengan mengubah kondisi dari >0ke <1dan menukar cabang-cabang kondisional, sehingga saya dapat menggunakan kembali angka literal, atau mungkin dengan menggunakan formula yang sama sekali berbeda, tapi saya cukup senang dengan betapa kompaknya sudah.

Penjelasan

Ini pada dasarnya mengimplementasikan rekursi yang diberikan dalam tantangan, meskipun menggunakan kasus dasar ! (- 1) =! 0 = 1 . n-1 dan n-2 dihitung dengan fungsi pendahulunya , dan hasil antara n-1 digunakan kembali di tiga tempat. Tidak ada yang lebih dari itu, jadi saya hanya akan dengan cepat melewati aliran kontrol:

               ─┐
               ╓┴╖
               ║f║
               ╙─╜

Ini adalah header fungsi yang memancarkan input fungsi dan merindukan baris terlampir. Ini segera mencapai pertigaan, yang hanya menduplikasi nilai.

        ┌┐┌┘╔═╗
        └┴┼─╢0║
          │ ╚═╝

The 0box hanya literal numerik. Persimpangan 4 arah menghitung dua fungsi: jalur yang mengarah dari bawah menghitung 0 <n , yang akan kita gunakan untuk menentukan kasus dasar. Jalur yang dibiarkan secara terpisah menghitung 0 << n (bergeser ke kiri), tetapi kami membuang nilai ini dengan konstruk Starkov .

         ┌┴╖ ╔═╗
         ┤?╟┐║1║
         ╘╤╝┘╚╤╝
          └───┘

Kami mengarahkan ini ke dalam kondisional tiga arah ?. Jika nilainya salah, kami mengembalikan hasil yang konstan 1. Ujung kanan longgar ?adalah output fungsi. Saya memutar sekitar 180 derajat di sini, sehingga orientasi relatif dari input dan output flebih nyaman di sisa program.

Jika kondisinya benar, maka nilai lainnya akan digunakan. Mari kita lihat jalan yang menuju ke cabang ini. (Perhatikan bahwa evaluasi Funciton sebenarnya malas sehingga cabang ini tidak akan pernah dievaluasi jika tidak diperlukan, yang memungkinkan terjadinya rekursi.)

        ┌─╖ 
      ┐┌┤♭╟┐
      ├┘╘═╝
      │
     ─┴┐

Di cabang lain kita pertama menghitung n-1 dan kemudian membagi jalan dua kali sehingga kita mendapatkan tiga salinan dari nilai (satu untuk koefisien perulangan, satu untuk subfaktorial pertama, yang terakhir untuk n-2 ).

┌─╖┌─╖
│f╟┤♭╟
╘╤╝╘═╝
 │┌─╖
 ││f╟
 │╘╤╝
 │┌┴╖
 ││+╟
 │╘╤╝
 └─┘ 

Seperti yang saya katakan, kami mengurangi satu salinan lagi dengan yang lain , lalu kami memberi makan n-1 dan n-2 secara rekursif fdan akhirnya menambahkan dua hasil bersama di +.

       ┐
       │
      ┌┴╖
     ┐│×╟
     │╘╤╝
     └─┘

Yang tersisa adalah mengalikan n-1 dengan ! (N-1) +! (N-2) .

Martin Ender
sumber
13

Oasis , 5 byte

Menggunakan formula yang diberikan oleh Martin. Kode:

+n<*X

Versi yang dibedah:

+n<*

dengan a(0) = 1dan a(1) = 0.

Penjelasan, a(n) =:

+       # Add the previous two terms, a(n - 1) + a(n - 2).
 n<     # Compute n - 1.
   *    # Multiply the top two elements.

Cobalah online!

Adnan
sumber
Trik yang bagus menggunakan X:-) BTW, apakah Anda sudah menerapkan ini ? Suatu hari kita tidak akan bisa lolos dengan hanya mengubah nilai awal
Luis Mendo
@LuisMendo Ya saya lakukan! Ini digunakan sebagai bendera perintah (di sini ada tautan ke halaman info). Terima kasih atas sarannya :).
Adnan
7

Jelly , 7 byte

R=Œ!Ḅċ0

Pendekatan ini membangun kekacauan, jadi agak lambat.

Cobalah online!

Bagaimana itu bekerja

R=Œ!Ḅċ0  Main link. Argument: n

R        Range; yield [1, ..., n].
  Œ!     Yield all permutations of [1, ..., n].
 =       Perform elementwise comparison of [1, ..., n] and each permutation.
    Ḅ    Unbinary; convert each result from base 2 to integer. This yields 0 for
         derangements, a positive value otherwise.
     ċ0  Count the number of zeroes.
Dennis
sumber
7

Brachylog (2), 11 byte

⟦₁{p:?\≠ᵐ}ᶜ

Cobalah online!

Penjelasan

Ini pada dasarnya hanya terjemahan langsung dari spec dari Bahasa Inggris ke Brachylog (dan dengan demikian memiliki keuntungan bahwa ia dapat dengan mudah dimodifikasi untuk menangani perubahan kecil pada spesifikasi, seperti menemukan jumlah kekacauan daftar tertentu).

⟦₁{p:?\≠ᵐ}ᶜ
⟦₁           Start with a list of {the input} distinct elements
  {      }ᶜ  Then count the number of ways to
   p         permute that list
      \      such that taking corresponding elements
    :?       in {the permutation} and the list of distinct elements
       ≠     gives different elements
        ᵐ    at every position

sumber
5

Bahasa dengan solusi bawaan

Mengikuti saran xnor, ini adalah jawaban CW di mana solusi sepele berdasarkan pada satu built-in untuk menghitung subfaktorial atau menghasilkan semua gangguan harus diedit.

Mathematica, 12 byte

Subfactorial
Martin Ender
sumber
sigh Mathematica ...
epicbob57
5

Python 3 , 35 32 byte

f=lambda n:n<1or(-1)**n+n*f(n-1)

Ini menggunakan relasi perulangan ! N = n! (N-1) + (-1) n dari jawaban Haskell @ Laikoni , dengan case dasar ! 0 = 1 .

Cobalah online!

Dennis
sumber
Saya pikir Anda juga dapat menggunakan persamaan lain yang diberikan di sini , yang akan menyelamatkan dua byte: f=lambda n:n<1or n*f(n-1)+(-1)**n.
Adnan
1
Tiga byte dengan sedikit pemesanan ulang. ;)
Dennis
1
Bagian yang menyenangkan dari perulangan ini adalah bahwa jika Anda mendorong casing dasar kembali ke n=-1, tidak masalah sama sekali nilai yang Anda gunakan. Itu bisa berguna untuk beberapa bahasa (misalnya dalam Mathematica Anda benar-benar bisa membiarkannya tidak terdefinisi jika itu menyimpan byte).
Martin Ender
5

M , 9 byte

o2!÷Øe+.Ḟ

Seperti yang Anda lihat dengan menghapus , M menggunakan matematika simbolik, sehingga tidak akan ada masalah presisi.

Cobalah online! Bukan solusi terpendek yang telah diposting, tetapi cepat .

Bagaimana itu bekerja

o2!÷Øe+.Ḟ  Main link. Argument: n

o2         Replace input 0 with 2, as the following formula fails for 0.
  !        Compute the factorial of n or 2.
   ֯e     Divide the result by e, Euler's natural number.
      +.   Add 1/2 to the result.
        Ḟ  Floor; round down to the nearest integer.
Dennis
sumber
5

MATL , 9 8 byte

:tY@-!As

Demikian pula dengan jawaban Jelly @ Dennis , ini benar-benar membangun permutasi dan menghitung berapa banyak dari mereka adalah kekacauan; jadi lambat.

Cobalah online!

:     % Input n implicitly: Push [1 2 ... n]
t     % Duplicate 
Y@    % Matrix of all permutations, each on a row
-     % Element-wise subtract. A zero in a row means that row is not a derangement
!     % Transpose
A     % True for columns that don't contain zeros
s     % Sum. Implicitly display
Luis Mendo
sumber
3

Matematika , 21 byte

Round@If[#>0,#!/E,1]&

Saya sangat baru dalam hal ini dan tidak tahu apa yang saya lakukan ...

Cobalah online!

Dennis
sumber
1
Dua alternatif pada jumlah byte yang sama: Round[(#/. 0->2)!/E]&dan ±0=1;±n_:=Round[n!/E](walaupun saya tidak tahu apakah Matematika mendukung pengkodean byte tunggal untuk file sumber seperti Mathematica).
Martin Ender
Yang pertama berfungsi dengan baik (saya pikir saya tahu apa fungsinya), tetapi Matematika tampaknya tidak mendukung ±yang kedua. Ini akan bekerja dengan f, tetapi dengan biaya dua byte.
Dennis
Lain pada byte yang sama menghitung: Round[#!/E]+1-Sign@#&. Nilai awal yang mengganggu ...!
Greg Martin
3

Ruby, 27 byte

f=->n{n<1?1:n*f[n-1]+~0**n}

~0**nlebih pendek dari (-1)**n!

m-chrzan
sumber
3

CJam (10 byte)

1qi{~*)}/z

Demo online .

Ini menggunakan pengulangan !n = n !(n-1) + (-1)^n , yang saya berasal dari n! / edan kemudian menemukan sudah di OEIS.

Pembedahan

Pengulangan menghitung (-1)^n !n, jadi kita perlu mengambil nilai absolut di akhir:

1     e# Push !0 to the stack
qi{   e# Read an integer n and loop from 0 to n-1
  ~   e#   Bitwise not takes i to -(i+1), so we can effectively loop from 1 to n
  *   e#   Multiply
  )   e#   Increment
}/
z     e# Take the absolute value
Peter Taylor
sumber
2

05AB1E , 8 byte

΃N*®Nm+

Cobalah online!

Penjelasan

Î         # initialize stack with 0 and input
 ƒ        # for N in range [0 ... input]:
  N*      # multiply top of stack with N
    ®Nm   # push (-1)^N
       +  # add
Emigna
sumber
2

MATLAB, 33 byte

@(n)(-1)^n*hypergeom([1 -n],[],1)

Fungsi Anonympus yang menggunakan rumus di Bagian 3 dari Pengaturan dan aplikasi oleh Mehdi Hassani.

Contoh penggunaan:

>> @(n)(-1)^n*hypergeom([1 -n],[],1)
ans = 
    @(n)(-1)^n*hypergeom([1,-n],[],1)
>> ans(6)
ans =
   265
Luis Mendo
sumber
2

JavaScript (ES6), 26 byte

f=n=>!n||n*f(n-1)-(~n%2|1)

Menggunakan relasi perulangan dari jawaban @ Laikoni. Di ES7 Anda dapat menyimpan byte dengan menggunakan +(-1)**nalih-alih -(~n%2|1).

Neil
sumber
2

PostScript, 81 76 69 byte

Berikut ini adalah implementasi dari kedua formula.

n * f (n-1) + (- 1) ^ n

/ f {dup 0 eq {pop 1} {dup dup 1 sub f mul exch 2 mod 2 mul 1 sub sub} ifelse} def

/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

Versi itu menghasilkan float. Jika perlu untuk mengeluarkan bilangan bulat:

/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp cvi add}ifelse}def

yang beratnya mencapai 73 byte.

Formula lainnya sedikit lebih panjang: 81 byte.

(n-1) * (f (n-1) + f (n-2))

/f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

Fungsi-fungsi ini mendapatkan argumennya dari stack, dan membiarkan hasilnya di stack.

Anda dapat menguji fungsi-fungsi, baik dalam file atau pada prompt PostScript interaktif (misalnya GhostScript) dengan

0 1 12{/i exch def [i i f] ==}for

keluaran

[0 1]
[1 0.0]
[2 1.0]
[3 2.0]
[4 9.0]
[5 44.0]
[6 265.0]
[7 1854.0]
[8 14833.0]
[9 133496.0]
[10 1334961.0]
[11 14684570.0]
[12 176214848.0]

Berikut adalah file PostScript lengkap yang membuat output ke layar atau halaman printer. (Komentar dalam PostScript dimulai dengan %).

%!PS-Adobe-3.0

% (n-1)*(f(n-1)+f(n-2))
% /f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

% n*f(n-1)+(-1)^n
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

% 0 1 12{/i exch def [i i f] ==}for

/FS 16 def              %font size
/LM 5 def               %left margin
/numst 12 string def    %numeric string buffer

/Newline{currentpoint exch pop FS sub LM exch moveto}def
/Courier findfont FS scalefont setfont
LM 700 moveto

(Subfactorials) Newline
0 1 12{
    dup numst cvs show (: ) show f numst cvs show Newline
}for
showpage
quit
PM 2Ring
sumber
1
-1 3 2 roll expsedikit lebih pendek dari adil exch 2 mod 2 mul 1 sub.
Peter Taylor
@PeterTaylor Begitulah! :) Saya lupa tentang exp: oops: Namun, ia mengembalikan float, dan saya pikir saya perlu menampilkan bilangan bulat agar sesuai dengan pertanyaan.
PM 2Ring
1
Saya pikir Anda masih bisa membuang cvidan melakukan penghematan. (Catatan: belum diuji, tetapi dari membaca dokumen saya pikir itu harus berhasil).
Peter Taylor
@PeterTaylor Ya, cviberfungsi, dan masih lebih pendek dari versi saya sebelumnya.
PM 2Ring
1

PHP, 69 Bytes

function f($i){return$i>1?$i*f($i-1)+(-1)**$i:1-$i;}echo f($argv[1]);

gunakan cara ini a(n) = n*a(n-1) + (-1)^n

Jörg Hülsermann
sumber
1
Anda hanya perlu memberikan fungsi, bukan program lengkap, sehingga Anda dapat menjatuhkan 17 karakter terakhir. Ada penghematan lebih lanjut dengan tidak memasukkan casing khusus 1. Saya pikir dua penghematan membawanya ke 47 byte.
Peter Taylor
1

PHP, 50 44

for(;$i++<$argn;)$n=++$n*$i-$i%2*2;echo$n+1;

Jalankan dengan echo <n> | php -nR '<code>

Keindahan a(n) = n*a(n-1) + (-1)^nadalah bahwa itu hanya tergantung pada nilai sebelumnya. Ini memungkinkan untuk diimplementasikan secara iteratif daripada secara rekursif. Ini menyimpan fungsi yang panjang deklarasi .

-6 bytes oleh @Titus. Terima kasih!

Christoph
sumber
-1 byte: $i++<$argv[1]. -2 byte: for(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;. (-3 byte dengan -Rdan $argn.)
Titus
@Titus seseorang bosan? : D maukah kamu memberi saya contoh untuk -Rdan $argn?
Christoph
1
Tidak bosan, tetapi ingin bermain golf. Lihat php.net/manual/de/features.commandline.options.php: echo <input> | php -nR '<code>'. contoh: codegolf.stackexchange.com/a/113046
Titus
1
@Itus apakah saya benar? ;-)
Christoph
0

Mathematica, 40 byte

±0=1;±1=0;±n_:=(n-1)(±(n-1)+±(n-2))

Yang datang pada 31 byte di bawah pengkodean ISO 8859-1 default.

A Simmons
sumber
0

C, 34 byte

a(n){return n?n*a(n-1)-n%2*2+1:1;}

Penjelasan:

a(n){                            } define a function called a of n
     return                     ;  make the function evaluate to...
            n?                :1   set the base case of 1 when n is 0
              n*a(n-1)             first half of the formula on the page
                      -n%2*2+1     (-1)**n
Bijan
sumber
0

R, 47 byte

n=scan();`if`(!n,1,floor(gamma(n+1)/exp(1)+.5))

Menggunakan rumus yang sama dengan jawaban Mego .

Metode alternatif, 52 byte menggunakan PerMallowsperpustakaan

n=scan();`if`(!n,1,PerMallows::count.perms(n,n,'h'))
Giuseppe
sumber
0

Sebenarnya , 18 byte

;!@ur⌠;!@0Dⁿ/⌡MΣ*≈

Cobalah online!

Penjelasan:

;!@ur⌠;!@0Dⁿ/⌡MΣ*≈
;                   duplicate input
 !                  n!
  @ur               range(0, n+1) (yields [0, n])
     ⌠;!@0Dⁿ/⌡M     for each i in range:
      ;               duplicate i
       !              i!
        @0Dⁿ          (-1)**i
            /         (-1)**i/i!
               Σ    sum
                *   multiply sum by n!
                 ≈  floor into int

Versi 12-byte yang akan berfungsi jika Sebenarnya memiliki lebih presisi:

;!╠@/1½+L@Y+

Cobalah online!

Tidak seperti semua jawaban lain (pada saat dikirim), solusi ini tidak menggunakan rumus rekursif atau rumus penjumlahan. Sebagai gantinya, ia menggunakan rumus berikut:

formula kekacauan

Formula ini relatif mudah diterapkan di Sebenarnya:

!╠@/1½+L
!         n!
 ╠        e
  @/      divide n! by e
    1½+   add 0.5
       L  floor

Sekarang, satu-satunya masalah adalah formula hanya berlaku untuk positif n. Jika Anda mencoba menggunakan n = 0, rumusnya salah menghasilkan 0. Ini mudah diperbaiki, namun: dengan menerapkan negasi boolean pada input dan menambahkannya ke output formula, output yang benar diberikan untuk semua non-negatif n. Dengan demikian, program dengan koreksi itu adalah:

;!╠@/1½+L@Y+
;             duplicate input
 !            n!
  ╠           e
   @/         divide n! by e
     1½+      add 0.5
        L     floor
         @Y   boolean negate the other copy of the input (1 if n == 0 else 0)
           +  add
Mego
sumber
Terus memberikan jawaban negatif untuk saya ...
Leaky Nun
@ LeakyNun Itu karena batas presisi. Untuk input besar (sekitar n = 100), (-1)**n/n!tidak dapat diwakili dengan float IEEE 754 presisi ganda. Itu bisa diterima sesuai tantangan.
Mego
Bahkan untuk n=4...
Leaky Nun
@ LeakyNun Oh. Saya tidak tahu mengapa saya menggunakan divisi lantai. Perbaiki sekarang.
Mego
16 byte
Leaky Nun
0

Ditumpuk , 30 byte

[:[#-::#-f\f+*]$not,\2<# !]@:f

Cobalah online!

Fungsi rekursif sederhana. Menggunakan fakta !n = not nuntuk itu n < 2. Sebut sebagai n f.

Conor O'Brien
sumber
0

Alice , 20 18 byte

1/o
k\i@/&wq*eqE+]

Cobalah online!

Penjelasan

Kegunaan ini rekursi dari Laikoni ini jawabannya , ! N = n! (N-1) + (-1) n . Mirip dengan jawaban Funciton, saya menggunakan kasus dasar ! (- 1) = 1 . Kami menempatkan 1 itu di tumpukan 1.. Lalu ini...

.../o
...\i@/...

... hanya kerangka I / O desimal yang biasa. Kode utamanya sebenarnya

&wq*eqE+]k

Rusak:

&w    Push the current IP address N times to the return address stack, which
      effectively begins a loop which will be executed N+1 times.
  q     Push the position of the tape head, which we're abusing as the
        iterator variable n.
  *     Multiply !(n-1) by n.
  e     Push -1.
  q     Retrieve n again.
  E     Raise -1 to the nth power.
  +     Add it to n*!(n-1).
  ]     Move the tape head to the right.
k     Jump back to the w, as long as there is still a copy of the return
      address on the return address stack. Otherwise, do nothing and exit
      the loop.
Martin Ender
sumber