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 Code-Golf , 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
quelle
Antworten:
Funktion , 336 Bytes
Die Byteanzahl setzt eine UTF-16-Codierung mit Stückliste voraus.
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:Ich denke, dass es möglich sein könnte, dies noch einmal zu tun, zB indem man die Kondition von
>0
auf ä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: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.
Das
0
Kä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 .Wir führen dies in die Drei-Wege-Bedingung
?
. Wenn der Wert falsch ist, geben wir das konstante Ergebnis zurück1
. Das lose Ende rechts von?
ist der Funktionsausgang. Ich drehe es hier um 180 Grad, damit die relative Ausrichtung von Eingabe und Ausgabef
im 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 ).
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 .
quelle
Oase , 5 Bytes
Verwendet die Formel von Martin. Code:
Präparierte Version:
mit
a(0) = 1
unda(1) = 0
.Erläuterung
a(n) =
:Probieren Sie es online!
quelle
X
:-) BTW, hast du implementieren diese noch? Eines Tages werden wir nicht in der Lage sein, nur die Anfangswerte zu ändernHaskell , 25 Bytes
Probieren Sie es online! Verwendet die andere Wiederholung von der OEIS- Seite.
quelle
Gelee , 7 Bytes
Dieser Ansatz konstruiert die Störungen, so dass es ziemlich langsam ist.
Probieren Sie es online!
Wie es funktioniert
quelle
Brachylog (2), 11 Bytes
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).
quelle
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
quelle
Python 3 ,
3532 BytesDies verwendet die Wiederholungsrelation ! N = n! (N-1) + (-1) n aus der @ Laikoni-Haskell-Antwort mit dem Basisfall ! 0 = 1 .
Probieren Sie es online!
quelle
f=lambda n:n<1or n*f(n-1)+(-1)**n
.n=-1
es 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).M , 9 Bytes
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
quelle
MATL ,
98 Bytesä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!
quelle
Mathematik , 21 Bytes
Ich bin sehr neu in diesem Bereich und habe keine Ahnung, was ich tue ...
Probieren Sie es online!
quelle
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).±
. Es würde funktionierenf
, aber auf Kosten von zwei Bytes.Round[#!/E]+1-Sign@#&
. Ärgerliche Anfangswerte ...!Ruby, 27 Bytes
~0**n
ist kürzer als(-1)**n
!quelle
CJam (10 Bytes)
Online-Demo .
Dies nutzt die Wiederholung
!n = n !(n-1) + (-1)^n
, die ich abgeleitetn! / e
und 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:quelle
05AB1E , 8 Bytes
Probieren Sie es online!
Erläuterung
quelle
MATLAB, 33 Bytes
Anonympus-Funktion, die die Formel in Abschnitt 3 von Derangements und Anwendungen von Mehdi Hassani verwendet.
Beispiel Verwendung:
quelle
JavaScript (ES6), 26 Byte
Verwendet die Wiederholungsrelation aus @ Laikonis Antwort. In ES7 können Sie ein Byte speichern, indem Sie
+(-1)**n
anstelle von verwenden-(~n%2|1)
.quelle
PostScript,
817669 BytesHier 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} defDiese Version gibt einen Float aus. Wenn eine Ganzzahl ausgegeben werden muss:
das wiegt bei 73 Bytes.
Die andere Formel ist etwas länger: 81 Bytes.
(n-1) * (f (n-1) + f (n-2))
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
Ausgabe
Hier ist eine vollständige PostScript-Datei, die die Ausgabe auf dem Bildschirm oder einer Druckerseite darstellt. (Kommentare in PostScript beginnen mit
%
).quelle
-1 3 2 roll exp
ist etwas kürzer alsexch 2 mod 2 mul 1 sub
.exp
Folgendes vergessen : oops: Es wird jedoch ein Float zurückgegeben, und ich denke, ich muss eine Ganzzahl ausgeben, um der Frage zu entsprechen.cvi
und eine Ersparnis machen. (Hinweis: ungetestet, aber nach dem Lesen des Dokuments sollte es funktionieren).cvi
funktioniert und ist immer noch kürzer als meine vorherige Version.PHP, 69 Bytes
benutze diesen Weg
a(n) = n*a(n-1) + (-1)^n
quelle
PHP,
5044Laufen Sie mit
echo <n> | php -nR '<code>
Das Schöne daran
a(n) = n*a(n-1) + (-1)^n
ist, 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 !
quelle
$i++<$argv[1]
. -2 Bytesfor(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;
. (-3 Bytes mit-R
und$argn
.)-R
und zu geben$argn
?Mathematica, 40 Bytes
Dies entspricht 31 Byte bei der Standardkodierung nach ISO 8859-1.
quelle
C 34 Bytes
Erläuterung:
quelle
R, 47 Bytes
Verwendet die gleiche Formel wie Megos Antwort .
Alternative Methode, 52 Bytes unter Verwendung der
PerMallows
Bibliothekquelle
Eigentlich 18 Bytes
Probieren Sie es online!
Erläuterung:
Eine 12-Byte-Version, die funktionieren würde, wenn sie tatsächlich präziser wäre:
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:
Diese Formel ist relativ einfach in Actually zu implementieren:
Das einzige Problem ist, dass die Formel nur für positiv gilt
n
. Wenn Sie versuchen, zu verwendenn = 0
, ergibt die Formel falsch0
. 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 angegebenn
. Das Programm mit dieser Korrektur lautet also:quelle
n = 100
)(-1)**n/n!
nicht mit doppeltgenauen IEEE 754-Floats dargestellt werden. Das ist der Herausforderung entsprechend akzeptabel.n=4
...Gestapelt , 30 Bytes
Probieren Sie es online!
Einfache rekursive Funktion. Nutzt die Tatsache, dass
!n = not n
fürn < 2
. Anrufen alsn f
.quelle
Alice ,
20 bis18 BytesProbieren 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...... ist nur das übliche dezimale E / A-Framework. Der Hauptcode ist eigentlich
Heruntergebrochen:
quelle