W subfactorial lub rencontres numery ( A000166 ) są sekwencje o numerach podobnych do silni liczb, które pojawiają się w kombinatoryki permutacji. W szczególności n th subfactorial ! N daje liczbę zaburzeniami z zestawem n elementów. Wykolejenie to permutacja, w której żaden element nie pozostaje w tej samej pozycji. Podfaktor można zdefiniować za pomocą następującej relacji powtarzalności:

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

W rzeczywistości ta sama relacja powtarzalności obowiązuje dla silni, ale dla podfrakcji zaczynamy od:

!0 = 1
!1 = 0

^{(Dla silni mielibyśmy oczywiście 1! = 1 ).}

Twoim zadaniem jest obliczenie ! N , biorąc pod uwagę n .

Zasady

Podobnie jak silnia, podfaktor rośnie bardzo szybko. W porządku, jeśli twój program może obsługiwać tylko takie dane wejściowe n , że ! N może być reprezentowany przez rodzimy typ liczbowy twojego języka. Jednak twój algorytm musi teoretycznie działać dla dowolnego n . Oznacza to, że możesz założyć, że wyniki całkowite i wartość pośrednia mogą być reprezentowane dokładnie przez Twój język. Zauważ, że wyklucza to stałą e, jeśli jest przechowywana lub obliczana ze skończoną precyzją.

Wynik musi być dokładną liczbą całkowitą (w szczególności nie można przybliżać wyniku za pomocą notacji naukowej).

Możesz napisać program lub funkcję i użyć dowolnej ze standardowych metod odbierania danych wejściowych i dostarczania danych wyjściowych.

Możesz używać dowolnego języka programowania , ale pamiętaj, że te luki są domyślnie zabronione.

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Przypadki testowe

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

Funciton , 336 bajtów

Liczba bajtów zakłada kodowanie UTF-16 za pomocą BOM.

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

Definiuje to funkcję, fktóra przyjmuje jedną liczbę całkowitą i wysyła inną liczbę całkowitą przy skręcie o 90 stopni w lewo. Działa dla dowolnie dużych nakładów.

Wypróbuj online!

Biorąc pod uwagę, że jest to Funciton, jest nawet dość szybki (n = 20 zajmuje około 14 sekund na TIO). Główne spowolnienie wynika z podwójnej rekurencji, ponieważ nie sądzę, że interpreter Funciton automatycznie zapamiętuje funkcje.

Niestety, niektóre czcionki o stałej szerokości nie mają prawidłowej szerokości ♭i / lub wstawiają małe odstępy między wierszami. Oto zrzut ekranu kodu z TIO w całej krasie:

Wydaje mi się, że można jeszcze trochę zagrać w golfa, np. Zmieniając warunek z >0na <1i zamieniając gałęzie warunkowe, abym mógł ponownie użyć literału liczb, lub może używając zupełnie innej formuły, ale jestem całkiem zadowolony z tego, jak kompaktowy jest już.

Wyjaśnienie

To w zasadzie implementuje rekurencję podaną w wyzwaniu, chociaż wykorzystuje podstawowy przypadek ! (- 1) =! 0 = 1 . n-1 i n-2 są obliczane z funkcją poprzednika ♭, a wynik pośredni n-1 jest ponownie wykorzystywany w trzech miejscach. Nie ma o wiele więcej, więc po prostu szybko przejdę przez kontrolę:

               ─┐
               ╓┴╖
               ║f║
               ╙─╜

Jest to nagłówek funkcji, która emituje wejściowe z funkcji n długo dołączony linii. To natychmiast dochodzi do trójnika, który po prostu powiela wartość.

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

0Box jest tylko dosłowne numeryczny. Łącznik 4-kierunkowy oblicza dwie funkcje: ścieżka prowadząca od dołu oblicza 0 <n , której użyjemy do określenia przypadku podstawowego. Ścieżka prowadząca osobno w lewo oblicza 0 << n (przesunięcie w lewo), ale tę wartość odrzucamy wraz z konstrukcją Starkowa .

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

Wprowadzamy to do trójstronnej warunkowej ?. Jeśli wartość jest fałszywa, zwracamy stały wynik 1. Luźny koniec po prawej stronie ?jest wyjściem funkcji. Obracam go tutaj o 180 stopni, aby względna orientacja wejścia i wyjścia fbyła wygodniejsza w pozostałej części programu.

Jeśli warunek był spełniony, zostanie użyta inna wartość. Spójrzmy na ścieżkę prowadzącą do tej gałęzi. (Zauważ, że ocena Funcitona jest w rzeczywistości leniwa, więc ta gałąź nigdy nie będzie oceniana, jeśli nie będzie potrzebna, co umożliwia w pierwszej kolejności rekurencję).

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

W drugiej gałęzi najpierw obliczamy n-1, a następnie dwukrotnie dzielimy ścieżkę, aby otrzymać trzy kopie wartości (jedna dla współczynnika nawrotu, jedna dla pierwszego podfaktora, ostatnia dla n-2 ).

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

Jak powiedziałem, ponownie zmniejszamy jedną kopię drugą ♭, a następnie rekurencyjnie podajemy zarówno n-1, jak i n-2f i ostatecznie dodajemy oba wyniki razem do pliku +.

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

Pozostało nam pomnożyć n-1 przez ! (N-1) +! (N-2) .

Oaza , 5 bajtów

Korzysta ze wzoru podanego przez Martina. Kod:

+n<*X

Wersja przekrojowa:

+n<*

z a(0) = 1i a(1) = 0.

Objaśnienie a(n) =:

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

Wypróbuj online!

Haskell , 25 bajtów

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

Wypróbuj online! Używa drugiej wznowienia ze strony OEIS .

Galaretka , 7 bajtów

R=Œ!Ḅċ0

To podejście konstruuje odstępstwa, więc jest raczej powolne.

Wypróbuj online!

Jak to działa

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.

Brachylog (2), 11 bajtów

⟦₁{p:?\≠ᵐ}ᶜ

Wypróbuj online!

Wyjaśnienie

Jest to w zasadzie tylko bezpośrednie tłumaczenie specyfikacji z angielskiego na Brachylog (a zatem ma tę zaletę, że można ją łatwo zmodyfikować w celu obsługi niewielkich zmian w specyfikacji, takich jak znalezienie liczby odchyleń konkretnej listy).

⟦₁{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

Języki z wbudowanymi rozwiązaniami

Zgodnie z sugestią xnora jest to odpowiedź CW, w której należy edytować trywialne rozwiązania oparte na jednym wbudowanym narzędziu do obliczania podfrakcji lub wygenerowania wszystkich derangencji.

Mathematica, 12 bajtów

Subfactorial

Python 3 , 35 32 bajtów

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

Wykorzystuje to relację powtarzalności ! N = n! (N-1) + (-1) ⁿ z odpowiedzi Haskell @ Laikoni , z przypadkiem podstawowym ! 0 = 1 .

Wypróbuj online!

M , 9 bajtów

o2!÷Øe+.Ḟ

Jak widać po usunięciu Ḟ, M używa matematyki symbolicznej, więc nie będzie problemów z precyzją.

Wypróbuj online! Nie najkrótsze opublikowane rozwiązanie, ale szybkie .

Jak to działa

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.

MATL , 9 8 bajtów

:tY@-!As

Podobnie jak w przypadku odpowiedzi Jelly @Dennis , tak naprawdę buduje permutacje i liczy, ile z nich to odstępstwa; więc jest wolny.

Wypróbuj 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

Matematyka , 21 bajtów

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

Jestem bardzo nowy i nie mam pojęcia, co robię ...

Wypróbuj online!

Rubinowy, 27 bajtów

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

~0**njest krótszy niż (-1)**n!

CJam (10 bajtów)

1qi{~*)}/z

Demo online .

Wykorzystuje to nawrót !n = n !(n-1) + (-1)^n , z której zacząłem, n! / ea następnie odkryłem, że był już w OEIS.

Sekcja

Pętla oblicza (-1)^n !n, dlatego na końcu musimy przyjąć wartość bezwzględną:

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

05AB1E , 8 bajtów

΃N*®Nm+

Wypróbuj online!

Wyjaśnienie

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

MATLAB, 33 bajty

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

Funkcja anonimowa, która korzysta ze wzoru z Rozdziału 3 Derangements i aplikacji Mehdi Hassani.

Przykładowe zastosowanie:

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

JavaScript (ES6), 26 bajtów

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

Wykorzystuje relację powtarzalności z odpowiedzi @ Laikoni. W ES7 możesz zapisać bajt, używając +(-1)**nzamiast -(~n%2|1).

PostScript, 81 76 69 bajtów

Oto implementacje obu formuł.

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

/ f {dup 0 eq {pop 1} {dup dup 1 sub f mul Exchange 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

Ta wersja generuje liczbę zmiennoprzecinkową. Jeśli konieczne jest wyprowadzenie liczby całkowitej:

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

który waży 73 bajty.

Druga formuła jest nieco dłuższa: 81 bajtów.

(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

Funkcje te pobierają argument ze stosu i pozostawiają wynik na stosie.

Możesz przetestować funkcje w pliku lub w interaktywnym monitie PostScript (np. GhostScript) za pomocą

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

wydajność

[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]

Oto kompletny plik PostScript, który renderuje dane wyjściowe na ekran lub stronę drukarki. (Komentarze w PostScript zaczynają się od %).

%!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

PHP, 69 bajtów

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

użyj tego sposobu a(n) = n*a(n-1) + (-1)^n

PHP, 50 44

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

Biegnij z echo <n> | php -nR '<code>

Piękno a(n) = n*a(n-1) + (-1)^npolega na tym, że zależy to tylko od poprzedniej wartości. Pozwala to na iteracyjne zamiast rekurencyjne. To oszczędza długą deklarację funkcji .

-6 bajtów przez @Titus. Dzięki !

Mathematica, 40 bajtów

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

Który ma 31 bajtów przy domyślnym kodowaniu ISO 8859-1.

C, 34 bajty

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

Wyjaśnienie:

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

R, 47 bajtów

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

Używa tej samej formuły, co odpowiedź Mego .

Metoda alternatywna, 52 bajty przy użyciu PerMallowsbiblioteki

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

Właściwie 18 bajtów

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

Wypróbuj online!

Wyjaśnienie:

;!@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

Wersja 12-bajtowa, która działałaby, gdyby faktycznie miała większą precyzję:

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

Wypróbuj online!

W przeciwieństwie do wszystkich innych odpowiedzi (od momentu opublikowania), to rozwiązanie nie używa ani formuły rekurencyjnej, ani formuły sumowania. Zamiast tego używa następującej formuły:

Ta formuła jest stosunkowo łatwa do wdrożenia w rzeczywistości:

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

Jedyny problem polega na tym, że formuła ma tylko wartość dodatnią n. Jeśli spróbujesz użyć n = 0, formuła niepoprawnie się wyda 0. Można to jednak łatwo naprawić: poprzez zastosowanie negacji logicznej na wejściu i dodanie jej do wyniku formuły, poprawne dane wyjściowe są podawane dla wszystkich nieujemnych n. Zatem program z tą korektą to:

;!╠@/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

Skumulowane , 30 bajtów

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

Wypróbuj online!

Prosta funkcja rekurencyjna. Wykorzystuje fakt, że !n = not ndla n < 2. Jak zadzwonić n f.

Alice , 20 18 bajtów

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

Wypróbuj online!

Wyjaśnienie

Wykorzystuje rekursja z Laikoni na odpowiedź , ! N = N + (n-1) + (-1) ⁿ . Podobnie jak odpowiedź Funcitona, używam podstawowego przypadku ! (- 1) = 1 . Kładziemy 1 na stosie 1.. Wtedy to...

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

... to zwykła platforma dziesiętna we / wy. Główny kod jest w rzeczywistości

&wq*eqE+]k

Zepsuty:

&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.