Tor
Sie erhalten eine Ganzzahl n
( n > 1
). Sie müssen ausgegeben , wie viele Permutationen der ganzen Zahlen 1
zu n
gibt, die beim Start 1
, Ende an n
, und haben nicht zwei aufeinanderfolgende ganze Zahlen , die um 1 unterscheiden.
Wenn Sie alternativ das vollständige Diagramm erstellen K_n
und die Kanten des Pfads entfernen 1-2-3-...-n
, müssen Sie die Hamilton-Pfade von 1
bis n
im verbleibenden Diagramm zählen.
Die Beispiele werden f(n)
für eine Funktion verwendet, die n
die Anzahl der gültigen Permutationen ein- und ausgibt, aber Ihre Einreichung kann eine Funktion oder ein Programm sein.
Beispiele
Denn n = 6
eine mögliche Lösung ist1-3-5-2-4-6
Dies 1-3-5-2-6-4
ist jedoch keine gültige Lösung, da sie nicht mit endet 6
.
Tatsächlich n = 6
gibt es für nur 2 Lösungen ( 1-4-2-5-3-6
ist die andere).
Daher f(6) = 2
.
Denn n = 4
die einzigen Permutationen, die in 1
und enden, 4
sind 1-2-3-4
und 1-3-2-4
. In beiden 2
steht das neben dem 3
, was aufeinanderfolgende ganze Zahlen ergibt, die sich um 1 unterscheiden f(4) = 0
.
Testfälle
f(6) = 2
f(4) = 0
f(8) = 68
f(13) = 4462848
Gewinnkriterium
Dies ist Code-Golf, die kürzeste Antwort gewinnt.
quelle
[2..n-1]
keine Deltas von1
oder enthalten-1
, Sie müssen auch überprüfen, ob keine von ihnen2
mitn-1
... beginnt oder endetQ_ser:=z + 2 z^6 + 10 z^7 + 68 z^8 + 500 z^9 + 4174 z^10 + 38774 z^11 + 397584z^12 + 4462848 z^13 + 54455754 z^14
Ich verbringe einige Zeit damit, die Formeln zu verwenden, aber ich kann keine erstellen, die die Sequenz erzeugt. Es ist erstaunlich zu sehen, dass der Exponent von z die Eingabe der Formel und das Ergebnis der Multiplikationsfaktor ist. Diejenige, die die Formel von dort ableiten kann, kann eine mit der kürzesten Antwort in Bytes seinAntworten:
MATL , 16 Bytes
Probieren Sie es online!
Bei Eingaben übersteigt
12
es den Speicherplatz.Erläuterung
quelle
Mathematica, 58 Bytes, Polynom ( n ) Zeit
Wie es funktioniert
Anstatt mit brachialer Gewalt über Permutationen zu iterieren, verwenden wir die Einschluss-Ausschluss-Prinzip, um sie kombinatorisch zu zählen.
Sei S die Menge aller Permutationen von [1,…, n] mit σ 1 = 1, σ n = n , und sei S i die Menge der Permutationen σ ∈ S, so dass | σ i - σ i + 1 | = 1. Dann ist die Anzahl die wir suchen
| S | - | S 1 ≤ ≤ S n - 1 | = ≤ 2 ≤ k ≤ n + 1; 1 ≤ i 2 <⋯ < i k - 1 < n (-1) k - 2 | S i 2 ∩ ⋯ ∩ S i k - 1 |.
Nun ist | S i 2 ≤ ≤ S i k - 1 | hängt nur von k und von der Anzahl j von Läufen aufeinanderfolgender Indizes in [ i 1 , i 2 ,…, i k - 1 , i k ] ab, wobei wir der Einfachheit halber i 1 = 0 und i k festlegen = n . Speziell,
| S i 2 ≤ ≤ S i k - 1 | = 2 j - 2 ( n - k ) !, für 2 ≤ j ≤ k ≤ n ,
| S i 2 ≤ ≤ S i k - 1 | = 1, für j = 1, k = n + 1.
Die Anzahl solcher Indexmengen [ i 1 , i 2 ,…, i k - 1 , i k ] mit j Läufen ist
( K - 1 C j - 1 ) ( n - k C j - 2 ), für 2 ≤ j ≤ k ≤ n ,
1, für j = 1, k = n + 1.
Das Ergebnis ist dann
(-1) n - 1 + Σ 2 ≤ k ≤ n Σ 2 ≤ j ≤ k (-1) k - 2 ( k - 1 C j - 1 ) ( n - k C j - 2 ) 2 j - 2 ( n - k )!
Die innere Summe über j kann mit der hypergeometrischen 2 F 1 -Funktion geschrieben werden :
(–1) n - 1 + ≤ 2 ≤ k ≤ n (–1) k ( k - 1) 2 F 1 (2 - k , k - n ; 2; 2) ( n - k )!
auf die wir eine Pfaff-Transformation anwenden, mit der wir die Potenzen von −1 mit einem absoluten Wert abschätzen können:
(−1) n - 1 + ≤ 2 ≤ k ≤ n (−1) n ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k )!
= | - 1 + ≤ 1 ≤ k ≤ n ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k !) |.
Demo
quelle
Jelly ,
1716 BytesEine monadische Verbindung.
Probieren Sie es online!
Wie?
quelle
IỊṀ
gültig ist. Was-2
ist zum Beispiel , wenn dort eines der Deltas ist? Sie können mitIAỊṀ
für +1 beheben .x <= 1
.Japt ,
1918 BytesOnline testen! Ich würde nicht empfehlen, auf etwas größer als zu testen
10
.Erläuterung
quelle
1
.n > 1
.05AB1E , 17 Bytes
Probieren Sie es online!
quelle
¹1Š)˜
Speichert ein Byte.Haskell,
7665 Bytes11 Bytes dank @xnor gespeichert.
Wenn
Q_rec
wir das Ergebnis für auf Seite 7 von @ ChristiaanWesterbeeks Fund verwenden, erhalten wirIch verstehe nicht, wie ihr nächstes Ergebnis aussehen wird
ha
bezieht, aber nach dem Beschleunigen (zuerst durch Auswendiglernen, siehe frühere Versionen, dann wie unten) erhalte ich ihre Zahlen.Während das oben Genannte in Ordnung ist
n=20
, ist es wesentlich ein Beispiel, wie man keine Rekursion macht. Hier ist eine schnellere Version (nur fürn>=6
), die auch nur konstanten Speicher benötigt - wenn nur die Zahlen nicht weiter steigen würden ...Das gibt
Es ist kein Problem, es auch zu bekommen,
f 5000
aber ich möchte das Ergebnis nicht einfügen ...Übrigens ist es möglich, keine ausgefallene Mathematik zu verwenden und trotzdem keine (ultra-) rohe Gewalt anzuwenden. Anstatt alle Permutationen zu betrachten, betrachten Sie zunächst Teilpermutationen und erweitern Sie sie nur, wenn sie noch nicht ungültig sind. Es hat keinen Sinn, alle Permutationen zu betrachten, die mit beginnen
1 6 5
. Zweitens mögen1 3 5 7
und1 5 3 7
haben einige partielle Permutationen genau die gleichen gültigen Fortsetzungen. Behandeln Sie sie also zusammen. Mit diesen Ideen könnte ich die Werte bis zun=16
0,3s berechnen.quelle
f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2]
.Python, 125 Bytes
quelle
Mathematica, 66 Bytes
Erläuterung
Function
mit erstem argument#
.quelle
Javascript (ES6),
100747260 BytesUnten ist die Version vor der Golf-Meisterschaft von @PeterTaylor
Dank der Antwort von @ChristianSievers, die es geschafft hat, eine Haskell-Lösung aus einem Papier zu entwerfen , das ich nach dem googeln von '0, 2, 10, 68, 500, 4174, 38774, 397584' gefunden habe, ist hier eine Javascript-Version, die auch nicht permutiert.
Verwendung
quelle
f(n)
Zeitpunkt gefragtn>1
, sodass es keine Rolle spielt, wofür Sie zurückkehrenn=1
. Auch ich findef(1)=1
das richtig.n<6?n==1|0:
für eine weitere Zwei-Zeichen-Speicherung kombinieren .f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)
Brachylog , 26 Bytes
Probieren Sie es online!
Erläuterung
quelle
Python 3 ,
109107102 BytesProbieren Sie es online!
Es wurden vier Bytes entfernt, indem nicht versucht wurde, die Funktion in einer Zeile (wie von @shooqie vorgeschlagen) und ein weiteres Byte durch
abs
ein Quadrat zu ersetzen . (Benötigt Python 3.5+)quelle
Python 2 , 136 Bytes
-10 Bytes dank @ovs.
Probieren Sie es online!
quelle
Mathematica, 134 Bytes
Testfälle n: 2 bis 12
quelle
Python 2 , 105 Bytes
Probieren Sie es online!
Dies basiert auf der Arbeit von Philippe Flajolet, die von @Christiaan Westerbeek entdeckt wurde . Es ist viel schneller und zwei Bytes kürzer als meine Python 3-Lösung, die die möglichen Permutationen auflistet. (In Python 3
reduce
wurde ärgerlicherweise nach verschobenfunctools
.)Es gibt eine viel kürzere Version mit numpy's dot product, die jedoch sehr schnell überläuft und den Import von numpy erfordert. Aber wofür es sich lohnt:
quelle