Opis
Niech permutacja liczb całkowitych {1, 2, ..., n}
będzie nazywana minimalnie interpolowalną, jeśli żaden zestaw k+2
punktów (wraz z ich indeksami) nie spadnie na wielomian stopnia k
. To jest,
- Żadne dwa punkty nie spadają na linię poziomą (wielomian 0 stopni)
- Żadne trzy punkty nie spadają na linię (wielomian 1 stopnia)
- Żadne cztery punkty nie spadają na parabolę (wielomian 2-stopniowy)
- I tak dalej.
Wyzwanie
Napisz program, który oblicza sekwencję OEIS A301802 (n) , liczbę permutacji minimalnie interpolowanych {1, 2, ..., n}
dla n
jak największej.
Punktacja
Zmierzę Twój kod na moim komputerze (2,3 GHz Intel Core i5, 8 GB pamięci RAM) przy rosnących wejściach. Twój wynik będzie największym wejściem, który zajmuje mniej niż 1 minutę, aby uzyskać prawidłową wartość.
Przykład
Na przykład permutacja [1, 2, 4, 3]
jest minimalnie interpolowana, ponieważ
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.
Na ilustracji widać, że linie poziome (czerwone) mają co najwyżej jeden punkt, linie (niebieskie) mają co najwyżej dwa punkty, a parabole (zielone) mają trzy punkty.
Dane
Oto minimalnie interpolable permutacje dla n=3
, n=4
i 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]
Jeśli mój program jest poprawny, pierwsze kilka wartości a(n)
liczby minimalnie interpolowanych permutacji {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
źródło
Odpowiedzi:
DO#
Pobiera wartości
n
jako argumenty wiersza polecenia lub jeśli uruchamia się bez argumentów razy do siebien=10
. Kompilując jako „Release” w VS 2017 i działając na Intel Core i7-6700, obliczamn=9
w 1,2 sekundy, an=10
w 13,6 sekundy.n=11
to nieco ponad 2 minuty.FWIW:
źródło