Deranged! Combinatorics: Berechnen Sie das Subfactorial

25

Die subfactorialen oder rencontres-Zahlen ( A000166 ) sind eine Folge von Zahlen, die den faktoriellen Zahlen ähneln, die in der Kombinatorik von Permutationen auftreten. Insbesondere gibt das n- te Unterfaktor ! N die Anzahl der Abweichungen einer Menge von n Elementen an. Eine Störung ist eine Permutation, bei der kein Element an derselben Position verbleibt. Das Subfactorial kann über die folgende Wiederholungsrelation definiert werden:

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

Tatsächlich gilt dieselbe Wiederholungsrelation für die Fakultät, aber für die Unterfakultät, von der wir ausgehen:

!0 = 1
!1 = 0

(Für die Fakultät hätten wir natürlich 1! = 1. )

Ihre Aufgabe ist es,! N zu berechnen , gegeben n .

Regeln

Wie die Fakultät wächst auch die Unterfakultät sehr schnell. Es ist in Ordnung, wenn Ihr Programm Eingaben n nur so verarbeiten kann, dass ! N durch den nativen Zahlentyp Ihrer Sprache dargestellt werden kann. Ihr Algorithmus muss jedoch theoretisch für beliebiges n funktionieren . Das heißt, Sie können davon ausgehen, dass ganzzahlige Ergebnisse und Zwischenwerte genau durch Ihre Sprache dargestellt werden können. Beachten Sie, dass dies die Konstante e ausschließt, wenn sie mit endlicher Genauigkeit gespeichert oder berechnet wird.

Das Ergebnis muss eine genaue Ganzzahl sein (insbesondere können Sie das Ergebnis nicht mit wissenschaftlicher Notation approximieren).

Sie können ein Programm oder eine Funktion schreiben und eine der Standardmethoden zum Empfangen von Eingaben und zum Bereitstellen von Ausgaben verwenden.

Sie können jede Programmiersprache verwenden , beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind.

Das ist , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .

Testfälle

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
quelle
Verbunden.
Martin Ender

Antworten:

19

Funktion , 336 Bytes

Die Byteanzahl setzt eine UTF-16-Codierung mit Stückliste voraus.

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

Dies definiert eine Funktion f die eine ganze Zahl annimmt und eine weitere ganze Zahl bei einer 90-Grad-Drehung nach links ausgibt. Es funktioniert für beliebig große Eingaben.

Probieren Sie es online!

In Anbetracht dessen ist Funciton es sogar einigermaßen schnell (n = 20 dauert bei TIO ungefähr 14 Sekunden). Die Hauptverlangsamung resultiert aus der doppelten Rekursion, da der Funciton-Interpreter meiner Meinung nach keine Funktionen automatisch speichert.

Leider werden bei einigen Schriften mit nur einem Zeilenabstand zwischen den Zeilen und / oder kleinen Lücken keine korrekten Zeilenabstände eingefügt . Hier ist ein Screenshot des Codes von TIO in all seiner Schönheit:

Bildbeschreibung hier eingeben

Ich denke, dass es möglich sein könnte, dies noch einmal zu tun, zB indem man die Kondition von >0auf ändert<1 ändere und die Zweige der Bedingung vertausche, um das Zahlenliteral wiederzuverwenden, oder indem ich eine völlig andere Formel verwende, aber ich bin ziemlich zufrieden damit, wie kompakt es schon ist.

Erläuterung

Dies implementiert im Wesentlichen die in der Abfrage angegebene Rekursion, obwohl der Basisfall ! (- 1) =! 0 = 1 verwendet wird . n-1 und n-2 werden mit der Vorgängerfunktion berechnet , und das Zwischenergebnis n-1 wird an drei Stellen wiederverwendet. Da es nicht viel mehr gibt, gehe ich kurz den Kontrollfluss durch:

               ─┐
               ╓┴╖
               ║f║
               ╙─╜

Dies ist der Funktionskopf, der die Funktion des Eingang aussendet n lange die Leitung befestigt. Dies erreicht sofort die T-Kreuzung, die den Wert einfach dupliziert.

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

Das 0Kästchen ist nur ein numerisches Literal. Eine 4-Wege-Kreuzung berechnet zwei Funktionen: Der Pfad, der vom unteren Ende wegführt, berechnet 0 <n , anhand dessen wir den Basisfall bestimmen. Der Pfad, der separat nach links geht, berechnet 0 << n (eine Linksverschiebung), wir verwerfen diesen Wert jedoch mit dem Starkov-Konstrukt .

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

Wir führen dies in die Drei-Wege-Bedingung ? . Wenn der Wert falsch ist, geben wir das konstante Ergebnis zurück 1. Das lose Ende rechts von ?ist der Funktionsausgang. Ich drehe es hier um 180 Grad, damit die relative Ausrichtung von Eingabe und Ausgabe fim Rest des Programms bequemer ist.

Wenn die Bedingung erfüllt war, wird der andere Wert verwendet. Schauen wir uns den Pfad an, der zu diesem Zweig führt. (Beachten Sie, dass Funcitons Auswertung faul ist, so dass dieser Zweig niemals ausgewertet wird, wenn er nicht benötigt wird, was die Rekursion überhaupt erst möglich macht.)

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

Im anderen Zweig berechnen wir zuerst n-1 und teilen den Pfad dann zweimal auf, sodass wir drei Kopien des Werts erhalten (eine für den Koeffizienten der Wiederholung, eine für das erste Subfactorial, die letzte für n-2 ).

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

Wie ich bereits sagte, dekrementieren wir eine Kopie erneut mit einer anderen , geben dann rekursiv n-1 und n-2 einf und addieren schließlich die beiden Ergebnisse in der +.

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

Alles, was übrig bleibt, ist, n-1 mit ! (N-1) +! (N-2) zu multiplizieren .

Martin Ender
quelle
13

Oase , 5 Bytes

Verwendet die Formel von Martin. Code:

+n<*X

Präparierte Version:

+n<*

mit a(0) = 1 und a(1) = 0.

Erläuterung a(n) =:

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

Probieren Sie es online!

Adnan
quelle
Nizza Trick X:-) BTW, hast du implementieren diese noch? Eines Tages werden wir nicht in der Lage sein, nur die Anfangswerte zu ändern
Luis Mendo
@ LuisMendo Ja, ich habe! Es wird als Befehlsflag verwendet ( hier ist ein Link zur Infoseite). Danke für den Vorschlag :).
Adnan
7

Gelee , 7 Bytes

R=Œ!Ḅċ0

Dieser Ansatz konstruiert die Störungen, so dass es ziemlich langsam ist.

Probieren Sie es online!

Wie es funktioniert

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
quelle
7

Brachylog (2), 11 Bytes

⟦₁{p:?\≠ᵐ}ᶜ

Probieren Sie es online!

Erläuterung

Dies ist im Grunde genommen nur eine direkte Übersetzung der Spezifikation aus dem Englischen in Brachylog (und hat somit den Vorteil, dass sie leicht geändert werden kann, um kleine Änderungen an der Spezifikation vorzunehmen, z. B. das Ermitteln der Anzahl von Abweichungen einer bestimmten Liste).

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

quelle
5

Sprachen mit integrierten Lösungen

Nach dem Vorschlag von xnor ist dies eine CW-Antwort, in die triviale Lösungen, die auf einer einzigen integrierten Funktion zur Berechnung des Subfaktors oder zur Generierung aller Abweichungen basieren, bearbeitet werden sollten.

Mathematica, 12 Bytes

Subfactorial
Martin Ender
quelle
Seufzer Mathematica ...
epicbob57
5

Python 3 , 35 32 Bytes

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

Dies verwendet die Wiederholungsrelation ! N = n! (N-1) + (-1) n aus der @ Laikoni-Haskell-Antwort mit dem Basisfall ! 0 = 1 .

Probieren Sie es online!

Dennis
quelle
Ich denke , man kann auch die andere Gleichung verwenden hier , die zwei Bytes speichern würde: f=lambda n:n<1or n*f(n-1)+(-1)**n.
Adnan
1
Drei Bytes mit einer kleinen Neuordnung. ;)
Dennis
1
Der lustige Teil dieser Wiederholung ist, dass n=-1es egal ist, welchen Wert Sie verwenden , wenn Sie das Basisgehäuse zurückschieben . Dies kann für einige Sprachen nützlich sein (z. B. in Mathematica können Sie es tatsächlich undefiniert lassen, wenn dadurch Bytes gespeichert werden).
Martin Ender
5

M , 9 Bytes

o2!÷Øe+.Ḟ

Wie Sie durch Entfernen des sehen können , verwendet M symbolische Mathematik, so dass es keine Präzisionsprobleme gibt.

Probieren Sie es online! Nicht die kürzeste Lösung, die veröffentlicht wurde, aber schnell .

Wie es funktioniert

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
quelle
5

MATL , 9 8 Bytes

:tY@-!As

ähnlich zu bei der Antwort @Dennis 'Jelly werden hierdurch die Permutationen erstellt und es wird gezählt, wie viele von ihnen Störungen sind. also ist es langsam.

Probieren Sie es 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
quelle
3

Mathematik , 21 Bytes

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

Ich bin sehr neu in diesem Bereich und habe keine Ahnung, was ich tue ...

Probieren Sie es online!

Dennis
quelle
1
Zwei Alternativen bei gleicher Byteanzahl : Round[(#/. 0->2)!/E]&und ±0=1;±n_:=Round[n!/E](obwohl ich nicht weiß, ob Mathics Einzelbyte-Codierungen für Quelldateien wie Mathematica unterstützt).
Martin Ender
Der erste funktioniert gut (ich glaube, ich weiß, was er tut), aber der zweite scheint Mathics nicht zu unterstützen ±. Es würde funktionieren f, aber auf Kosten von zwei Bytes.
Dennis
Ein weiteres auf dem gleichen Byte zählen: Round[#!/E]+1-Sign@#&. Ärgerliche Anfangswerte ...!
Greg Martin
3

Ruby, 27 Bytes

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

~0**nist kürzer als (-1)**n!

m-chrzan
quelle
3

CJam (10 Bytes)

1qi{~*)}/z

Online-Demo .

Dies nutzt die Wiederholung !n = n !(n-1) + (-1)^n, die ich abgeleitet n! / eund dann entdeckt habe, war bereits in OEIS.

Präparation

Die Schleife berechnet (-1)^n !n, also müssen wir den absoluten Wert am Ende nehmen:

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
quelle
2

05AB1E , 8 Bytes

΃N*®Nm+

Probieren Sie es online!

Erläuterung

Î         # 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
quelle
2

MATLAB, 33 Bytes

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

Anonympus-Funktion, die die Formel in Abschnitt 3 von Derangements und Anwendungen von Mehdi Hassani verwendet.

Beispiel Verwendung:

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

JavaScript (ES6), 26 Byte

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

Verwendet die Wiederholungsrelation aus @ Laikonis Antwort. In ES7 können Sie ein Byte speichern, indem Sie +(-1)**nanstelle von verwenden -(~n%2|1).

Neil
quelle
2

PostScript, 81 76 69 Bytes

Hier sind Implementierungen beider Formeln.

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

Diese Version gibt einen Float aus. Wenn eine Ganzzahl ausgegeben werden muss:

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

das wiegt bei 73 Bytes.

Die andere Formel ist etwas länger: 81 Bytes.

(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

Diese Funktionen erhalten ihr Argument vom Stapel und belassen das Ergebnis auf dem Stapel.

Sie können die Funktionen entweder in einer Datei oder an einer interaktiven PostScript-Eingabeaufforderung (zB GhostScript) mit testen

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

Ausgabe

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

Hier ist eine vollständige PostScript-Datei, die die Ausgabe auf dem Bildschirm oder einer Druckerseite darstellt. (Kommentare in PostScript beginnen mit %).

%!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
quelle
1
-1 3 2 roll expist etwas kürzer als exch 2 mod 2 mul 1 sub.
Peter Taylor
@ PeterTaylor So ist es! :) Ich habe expFolgendes vergessen : oops: Es wird jedoch ein Float zurückgegeben, und ich denke, ich muss eine Ganzzahl ausgeben, um der Frage zu entsprechen.
PM 2Ring
1
Ich denke du kannst noch einficken cviund eine Ersparnis machen. (Hinweis: ungetestet, aber nach dem Lesen des Dokuments sollte es funktionieren).
Peter Taylor
@PeterTaylor Ja, cvifunktioniert und ist immer noch kürzer als meine vorherige Version.
PM 2Ring
1

PHP, 69 Bytes

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

benutze diesen Weg a(n) = n*a(n-1) + (-1)^n

Jörg Hülsermann
quelle
1
Sie müssen nur die Funktion angeben, nicht das vollständige Programm, damit Sie die letzten 17 Zeichen löschen können. Es gibt eine weitere Einsparung durch Eingabe ohne spezielle Gehäuse 1. Ich denke, die beiden Einsparungen verringern sie auf 47 Byte.
Peter Taylor
1

PHP, 50 44

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

Laufen Sie mit echo <n> | php -nR '<code>

Das Schöne daran a(n) = n*a(n-1) + (-1)^nist, dass es nur auf den vorherigen Wert ankommt. Dadurch kann es iterativ statt rekursiv implementiert werden. Dies erspart eine lange Funktionsdeklaration .

-6 Bytes von @Titus. Vielen Dank !

Christoph
quelle
-1 Byte: $i++<$argv[1]. -2 Bytes for(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;. (-3 Bytes mit -Rund $argn.)
Titus
@Titus hat sich jemand gelangweilt? : D Würde es Ihnen etwas ausmachen, mir ein Beispiel für -Rund zu geben $argn?
Christoph
1
Nicht gelangweilt, aber golfbegeistert. Siehe php.net/manual/de/features.commandline.options.php: echo <input> | php -nR '<code>'. Beispiel: codegolf.stackexchange.com/a/113046
Titus
1
@Titus habe ich es richtig verstanden? ;-)
Christoph
0

Mathematica, 40 Bytes

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

Dies entspricht 31 Byte bei der Standardkodierung nach ISO 8859-1.

Ein Simmons
quelle
0

C 34 Bytes

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

Erläuterung:

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
quelle
0

R, 47 Bytes

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

Verwendet die gleiche Formel wie Megos Antwort .

Alternative Methode, 52 Bytes unter Verwendung der PerMallowsBibliothek

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

Eigentlich 18 Bytes

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

Probieren Sie es online!

Erläuterung:

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

Eine 12-Byte-Version, die funktionieren würde, wenn sie tatsächlich präziser wäre:

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

Probieren Sie es online!

Im Gegensatz zu allen anderen Antworten (zum Zeitpunkt der Veröffentlichung) verwendet diese Lösung weder die rekursive Formel noch die Summenformel. Stattdessen wird die folgende Formel verwendet:

Störung Formel

Diese Formel ist relativ einfach in Actually zu implementieren:

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

Das einzige Problem ist, dass die Formel nur für positiv gilt n. Wenn Sie versuchen, zu verwenden n = 0, ergibt die Formel falsch 0. Dies lässt sich jedoch leicht beheben: Durch Anwenden der Booleschen Negation auf die Eingabe und Hinzufügen dieser zur Ausgabe der Formel wird die korrekte Ausgabe für alle nicht-negativen Werte angegeben n. Das Programm mit dieser Korrektur lautet also:

;!╠@/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
quelle
Gibt mir immer wieder negative Antworten ...
Undichte Nonne
@LeakyNun Das liegt an den Genauigkeitsgrenzen. Kann bei großen Eingaben (um n = 100) (-1)**n/n!nicht mit doppeltgenauen IEEE 754-Floats dargestellt werden. Das ist der Herausforderung entsprechend akzeptabel.
Mego
Auch für n=4...
Undichte Nonne
@LeakyNun Oh. Ich weiß nicht, warum ich Floored Division verwendet habe. Behebung jetzt.
Mego
16 Bytes
Undichte Nonne
0

Alice , 20 bis 18 Bytes

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

Probieren Sie es online!

Erläuterung

Dies verwendet die Rekursion von Laikoni Antwort , ! N = n! (N-1) + (-1) n . Ähnlich wie bei der Antwort von Funciton verwende ich den Basisfall ! (- 1) = 1 . Wir legen die 1 mit auf den Stapel 1.. Dann das...

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

... ist nur das übliche dezimale E / A-Framework. Der Hauptcode ist eigentlich

&wq*eqE+]k

Heruntergebrochen:

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