В subfactorial или Rencontres номер ( A000166 ) представляет собой последовательность чисел , подобных факторным числа , которые показывают в комбинаторике перестановок. В частности, n- й субфакториал ! N дает количество нарушений для набора из n элементов. Нарушение - это перестановка, в которой ни один элемент не остается в том же положении. Субфакториал может быть определен через следующее отношение повторения:

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

Фактически, то же самое рекуррентное отношение верно для факториала, но для субфакториала мы начинаем с:

!0 = 1
!1 = 0

^{(Для факториала у нас, конечно, 1! = 1. )}

Ваша задача - вычислить ! N , учитывая n .

правила

Как и факториал, субфакториал растет очень быстро. Хорошо, если ваша программа может обрабатывать только входные данные n , так что ! N может быть представлен типом номера вашего языка. Тем не менее, ваш алгоритм теоретически должен работать для произвольного n . Это означает, что вы можете предполагать, что интегральные результаты и промежуточные значения могут быть представлены именно вашим языком. Обратите внимание, что это исключает постоянную e, если она хранится или вычисляется с конечной точностью.

Результат должен быть точным целым числом (в частности, вы не можете приблизить результат с научной нотацией).

Вы можете написать программу или функцию и использовать любой из стандартных методов получения ввода и предоставления вывода.

Вы можете использовать любой язык программирования , но учтите, что эти лазейки по умолчанию запрещены.

Это код-гольф , поэтому самый короткий действительный ответ - измеренный в байтах - выигрывает.

Тестовые случаи

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 байт

Число байтов предполагает кодировку UTF-16 с BOM.

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

Это определяет функцию, fкоторая принимает одно целое число и выводит другое целое число при повороте на 90 градусов влево. Это работает для произвольно больших входов.

Попробуйте онлайн!

Учитывая, что это Funciton, он даже достаточно быстрый (n = 20 занимает около 14 секунд на TIO). Основное замедление происходит из-за двойной рекурсии, поскольку я не думаю, что интерпретатор Funciton автоматически запоминает функции.

К сожалению, некоторые моноширинные шрифты неправильно моноширируют ♭и / или не вставляют небольшие пропуски между строками. Вот скриншот кода от TIO во всей его красе:

Я думаю, что можно было бы еще немного поиграть в это, например, изменив условие с >0на <1и поменяв местами условные ветви, чтобы я мог повторно использовать числовой литерал, или, возможно, используя совершенно другую формулу, но я вполне доволен тем, насколько он компактен.

объяснение

Это в основном реализует рекурсию, данную в вызове, хотя и использует базовый вариант ! (- 1) =! 0 = 1 . n-1 и n-2 вычисляются с помощью функции-предшественника ♭, а промежуточный результат n-1 повторно используется в трех местах. В этом нет ничего особенного, поэтому я просто быстро пройду поток управления:

               ─┐
               ╓┴╖
               ║f║
               ╙─╜

Это заголовок функции, который выдает вход функции n по присоединенной строке. Это немедленно достигает T-перехода, который просто дублирует значение.

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

0Окно просто числовой литерал. Четырехсторонний переход вычисляет две функции: путь, ведущий снизу, вычисляет 0 <n , который мы будем использовать для определения базового варианта. Путь, идущий влево отдельно, вычисляет 0 << n (сдвиг влево), но мы отбрасываем это значение с помощью конструкции Старкова .

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

Мы приведем это в трехстороннее условное ?. Если значение равно false, мы возвращаем постоянный результат 1. Свободный конец справа от ?выхода функции. Здесь я поворачиваю его на 180 градусов, чтобы относительная ориентация ввода и вывода была fболее удобной в остальной части программы.

Если условие было выполнено, то будет использоваться другое значение. Давайте посмотрим на путь, который ведет к этой ветви. (Обратите внимание, что оценка Funciton на самом деле ленива, так что эта ветвь никогда не будет оцениваться, если она не нужна, что делает рекурсию возможной в первую очередь.)

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

В другой ветви мы сначала вычисляем n-1, а затем дважды разделяем путь, чтобы получить три копии значения (одну для коэффициента повторения, одну для первого субфакториала, последнюю для n-2 ).

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

Как я уже сказал, мы снова уменьшаем одну копию другой ♭, затем рекурсивно подаем n-1 и n-2f и, наконец, добавляем два результата вместе в +.

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

Осталось только умножить n-1 на ! (N-1) +! (N-2) .

Оазис , 5 байт

Использует формулу, данную Мартином. Код:

+n<*X

Разобранная версия:

+n<*

с a(0) = 1и a(1) = 0.

Объяснение a(n) =:

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

Попробуйте онлайн!

Haskell , 25 байт

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

Попробуйте онлайн! Использует другое повторение со страницы OEIS .

Желе , 7 байт

R=Œ!Ḅċ0

Такой подход создает недостатки, поэтому он довольно медленный.

Попробуйте онлайн!

Как это работает

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.

Брахилог (2), 11 байт

⟦₁{p:?\≠ᵐ}ᶜ

Попробуйте онлайн!

объяснение

По сути, это всего лишь прямой перевод спецификации с английского языка на брахилог (и, следовательно, имеет то преимущество, что его можно легко модифицировать для обработки небольших изменений в спецификации, таких как поиск количества отклонений в конкретном списке).

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

Языки со встроенными решениями

Следуя предложению xnor, это ответ CW, в котором должны быть отредактированы тривиальные решения, основанные на единственном встроенном для вычисления субфакториала или генерации всех неисправностей.

Mathematica, 12 байт

Subfactorial

Python 3 , 35 32 байта

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

При этом используется рекуррентное соотношение ! N = n! (N-1) + (-1) ⁿ из ответа @ Laikoni's Haskell с базовым регистром ! 0 = 1 .

Попробуйте онлайн!

М , 9 байт

o2!÷Øe+.Ḟ

Как вы можете видеть, удалив Ḟ, M использует символическую математику, поэтому проблем с точностью не будет.

Попробуйте онлайн! Не самое короткое решение, которое было опубликовано, но быстро .

Как это работает

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 байт

:tY@-!As

Аналогично ответу желе @Dennis ' , это на самом деле создает перестановки и подсчитывает, сколько из них являются отклонениями; так медленно

Попробуйте онлайн!

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

Математика , 21 байт

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

Я очень новичок в этом и понятия не имею, что я делаю ...

Попробуйте онлайн!

Рубин, 27 байт

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

~0**nкороче чем (-1)**n!

CJam (10 байт)

1qi{~*)}/z

Демо онлайн .

При этом используется повторение !n = n !(n-1) + (-1)^n, которое я получил, n! / eа затем обнаружил, что оно уже было в OEIS.

рассечение

Цикл вычисляет (-1)^n !n, поэтому нам нужно взять абсолютное значение в конце:

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 байтов

΃N*®Nm+

Попробуйте онлайн!

объяснение

Î         # 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 байта

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

Функция Anonympus, которая использует формулу в Разделе 3 « Нарушения и приложения» » Мехди Хассани.

Пример использования:

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

JavaScript (ES6), 26 байт

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

Использует рекуррентное соотношение из ответа @ Laikoni. В ES7 вы можете сохранить байт, используя +(-1)**nвместо -(~n%2|1).

PostScript, 81 76 69 байт

Вот реализации обеих формул.

п * е (п-1) + (- 1) ^ п

/ 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

Эта версия выводит число с плавающей точкой. Если необходимо вывести целое число:

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

который весит 73 байта.

Другая формула немного длиннее: 81 байт.

(П-1) * (е (п-1) + F (п-2))

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

Эти функции получают свои аргументы из стека и оставляют результат в стеке.

Вы можете проверить функции в файле или в интерактивном приглашении PostScript (например, GhostScript) с помощью

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

выход

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

Вот полный файл PostScript, который отображает вывод на экран или страницу принтера. (Комментарии в PostScript начинаются с %).

%!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 байт

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

использовать этот способ a(n) = n*a(n-1) + (-1)^n

PHP, 50 44

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

Бежать с echo <n> | php -nR '<code>

Прелесть в a(n) = n*a(n-1) + (-1)^nтом, что это зависит только от предыдущего значения. Это позволяет реализовать его итеративно, а не рекурсивно. Это экономит долго функцию декларации.

-6 байт @Titus. Благодарность !

Mathematica, 40 байт

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

Который входит в 31 байт в кодировке по умолчанию ISO 8859-1.

C, 34 байта

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

Объяснение:

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 байт

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

Использует ту же формулу, что и ответ Мего .

Альтернативный метод, 52 байта с использованием PerMallowsбиблиотеки

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

На самом деле , 18 байт

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

Попробуйте онлайн!

Объяснение:

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

12-байтовая версия, которая работала бы, если бы на самом деле имела большую точность:

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

Попробуйте онлайн!

В отличие от всех других ответов (на момент публикации), это решение не использует ни рекурсивную формулу, ни формулу суммирования. Вместо этого он использует следующую формулу:

Эту формулу относительно легко реализовать на самом деле:

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

Теперь единственная проблема в том, что формула верна только для положительного n. Если вы попытаетесь использовать n = 0, формула неверно дает 0. Однако это легко исправить: применяя логическое отрицание к входу и добавляя его к выходу формулы, правильный вывод дается для всех неотрицательных значений n. Таким образом, программа с этой коррекцией:

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

С накоплением , 30 байтов

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

Попробуйте онлайн!

Простая рекурсивная функция. Использует тот факт, что !n = not nдля n < 2. Звоните как n f.

Алиса , 20 18 байт

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

Попробуйте онлайн!

объяснение

При этом используется рекурсия от Laikoni отвечают , ! П = п! (П-1) + (-1) ^п . Как и в ответе Funciton, я использую базовый вариант ! (- 1) = 1 . Мы помещаем это 1 в стек с 1.. Тогда это ...

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

... это просто обычный десятичный каркас ввода / вывода. Основной код на самом деле

&wq*eqE+]k

Сломано:

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