Beschreibung
Lassen Sie eine Permutation der ganzen Zahlen {1, 2, ..., n}
als minimal interpolierbar bezeichnet werden, wenn keine k+2
Punktmenge (zusammen mit ihren Indizes) auf ein Polynom vom Grad fällt k
. Das ist,
- Keine zwei Punkte fallen auf eine horizontale Linie (0-Grad-Polynom)
- Es fallen keine drei Punkte auf eine Linie (1-Grad-Polynom)
- Keine vier Punkte fallen auf eine Parabel (2-Grad-Polynom)
- Und so weiter.
Herausforderung
Ein Programm schreiben , die OEIS Sequenz berechnet A301802 (n) , die Anzahl der Permutationen von minimal interpolierbar {1, 2, ..., n}
für n
als groß wie möglich.
Wertung
Ich werde Ihren Code auf meinem Computer (2,3 GHz Intel Core i5, 8 GB RAM) mit zunehmenden Eingaben timen. Ihre Punktzahl ist die größte Eingabe, die weniger als 1 Minute dauert, um den richtigen Wert auszugeben.
Beispiel
Beispielsweise ist die Permutation [1, 2, 4, 3]
wegen minimal interpolierbar
the terms together with their indices
[(1, 1), (2, 2), (3, 4), (4, 3)]
have the property that
(0) No two points have the same y-value.
(1) No three points lie on a line.
(2) No four points lie on a parabola.
In der Abbildung ist zu sehen, dass die horizontalen Linien (rot) höchstens einen Punkt aufweisen, die Linien (blau) höchstens zwei Punkte aufweisen und die Parabeln (grün) drei Punkte aufweisen.
Daten
Hier sind die minimal interpolierbar Permutationen für n=3
, n=4
und n=5
:
n = 3: [1,3,2],[2,1,3],[2,3,1],[3,1,2]
n = 4: [1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],[3,2,4,1],[3,4,1,2],[3,4,2,1],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2]
n = 5: [1,2,5,3,4],[1,3,2,5,4],[1,3,4,2,5],[1,4,2,3,5],[1,4,3,5,2],[1,4,5,2,3],[1,4,5,3,2],[1,5,3,2,4],[2,1,4,3,5],[2,3,1,4,5],[2,3,5,1,4],[2,3,5,4,1],[2,4,1,5,3],[2,4,3,1,5],[2,4,5,1,3],[2,5,1,3,4],[2,5,1,4,3],[2,5,3,4,1],[2,5,4,1,3],[3,1,4,5,2],[3,1,5,2,4],[3,1,5,4,2],[3,2,5,1,4],[3,2,5,4,1],[3,4,1,2,5],[3,4,1,5,2],[3,5,1,2,4],[3,5,1,4,2],[3,5,2,1,4],[4,1,2,5,3],[4,1,3,2,5],[4,1,5,2,3],[4,1,5,3,2],[4,2,1,5,3],[4,2,3,5,1],[4,2,5,1,3],[4,3,1,2,5],[4,3,1,5,2],[4,3,5,2,1],[4,5,2,3,1],[5,1,3,4,2],[5,2,1,3,4],[5,2,1,4,3],[5,2,3,1,4],[5,2,4,3,1],[5,3,2,4,1],[5,3,4,1,2],[5,4,1,3,2]
Wenn mein Programm korrekt ist, die ersten paar Werte von a(n)
, die Anzahl der minimal interpolierbaren Permutationen von {1, 2, ..., n}
:
a(1) = 1
a(2) = 2
a(3) = 4
a(4) = 18
a(5) = 48
a(6) = 216
a(7) = 584
a(8) = 2870
quelle
Antworten:
C #
Nimmt Werte von
n
als Kommandozeilenargumente, oder wenn ohne Argumente ausgeführt, mal sich bis zun=10
. Als "Release" in VS 2017 kompiliert und auf einem Intel Core i7-6700 ausgeführt, rechne ichn=9
in 1,2 Sekunden undn=10
in 13,6 Sekunden.n=11
ist etwas mehr als 2 Minuten.FWIW:
quelle