Deranged! Комбинаторика: вычислить субфакториал

25

В 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
Мартин Эндер
источник
Связанный.
Мартин Эндер

Ответы:

19

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

Мартин Эндер
источник
13

Оазис , 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.

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

Аднан
источник
Хороший трюк с использованием X:-) Кстати, вы уже реализовали это ? На днях мы не сможем сойти с рук, просто изменив начальные значения
Луис Мендо,
@ LuisMendo Да, я сделал! Он используется как флаг команды ( здесь ссылка на информационную страницу). Спасибо за предложение :).
Аднан
7

Желе , 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.
Деннис
источник
7

Брахилог (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

источник
5

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

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

Mathematica, 12 байт

Subfactorial
Мартин Эндер
источник
вздох Mathematica ...
epicbob57
5

Python 3 , 35 32 байта

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

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

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

Деннис
источник
Я думаю , вы также можете использовать другие уравнения , приводимые здесь , что позволит сэкономить два байта: f=lambda n:n<1or n*f(n-1)+(-1)**n.
Аднан
1
Три байта с небольшим переупорядочением. ;)
Денис
1
Самое интересное в этом повторении состоит в том, что если вы вернете базовый вариант назад n=-1, совершенно не имеет значения, какое значение вы используете. Это может быть полезно для некоторых языков (например, в Mathematica вы можете оставить его неопределенным, если это сохранит какие-либо байты).
Мартин Эндер
5

М , 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.
Деннис
источник
5

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
Луис Мендо
источник
3

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

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

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

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

Деннис
источник
1
Две альтернативы с одинаковым количеством байтов: Round[(#/. 0->2)!/E]&и ±0=1;±n_:=Round[n!/E](хотя я не знаю, поддерживает ли Mathics однобайтовые кодировки для исходных файлов, как это делает Mathematica).
Мартин Эндер
Первый работает хорошо (я думаю, я знаю, что он делает), но Mathics, кажется, не поддерживает ±во втором. Это будет работать с f, но за счет двух байтов.
Денис
Другие в том же байте рассчитывать: Round[#!/E]+1-Sign@#&. Раздражающие начальные значения ...!
Грег Мартин,
3

Рубин, 27 байт

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

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

м-chrzan
источник
3

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
Питер Тейлор
источник
2

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
Луис Мендо
источник
2

JavaScript (ES6), 26 байт

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

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

Нил
источник
2

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
PM 2Ring
источник
1
-1 3 2 roll expнемного короче exch 2 mod 2 mul 1 sub.
Питер Тейлор
@PeterTaylor Так оно и есть! :) Я забыл о exp: oops: Однако, он возвращает число с плавающей запятой, и я думаю, что мне нужно вывести целое число, чтобы соответствовать вопросу.
PM 2Ring
1
Я думаю, что вы все еще можете вмешаться cviи сделать экономию. (Примечание: не проверено, но, читая документ, я думаю, что это должно работать).
Питер Тейлор
@PeterTaylor Да, cviработает, и все еще короче, чем моя предыдущая версия.
PM 2Ring
1

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

Йорг Хюльсерманн
источник
1
Вам нужно только дать функцию, а не полную программу, чтобы вы могли сбросить последние 17 символов. Существует дополнительная экономия за счет ввода не в специальном корпусе 1. Я думаю, что две экономии уменьшают до 47 байтов.
Питер Тейлор
1

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. Благодарность !

Christoph
источник
-1 байт: $i++<$argv[1]. -2 байт: for(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;. (-3 байта с -Rи $argn.)
Титус
@ Титус кому-то стало скучно? : D не могли бы вы привести пример для -Rа $argn?
Кристоф
1
Не скучно, но жаждет гольфа. См. Php.net/manual/de/features.commandline.options.php: echo <input> | php -nR '<code>'. пример: codegolf.stackexchange.com/a/113046
Титус
1
@ Правильно ли я понял? ;-)
Кристоф
0

Mathematica, 40 байт

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

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

Симмонс
источник
0

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
Bijan
источник
0

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'))
Giuseppe
источник
0

На самом деле , 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
Mego
источник
Продолжает давать отрицательные ответы для меня ...
Leaky Nun
@ LeakyNun Это из-за пределов точности. Для больших входов (вокруг n = 100) (-1)**n/n!не может быть представлено с плавающей точкой двойной точности IEEE 754. Это приемлемо в соответствии с проблемой.
Mego
Даже для n=4...
Утренняя монахиня
@ LeakyNun Ох. Я не знаю, почему я использовал этажное подразделение. Исправляем это сейчас.
Mego
16 байт
Утренняя монахиня
0

Алиса , 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.
Мартин Эндер
источник