16
0
Description
Let a permutation of the integers {1, 2, ..., n}
be called minimally interpolable if no set of k+2
points (together with their indices) fall on a polynomial of degree k
.
That is,
- No two points fall on a horizontal line (0-degree polynomial)
- No three points fall on a line (1-degree polynomial)
- No four points fall on a parabola (2-degree polynomial)
- Et cetera.
Challenge
Write a program that computes OEIS sequence A301802(n), the number of minimally interpolable permutations of {1, 2, ..., n}
for n
as a large as possible.
Scoring
I will time your code on my computer (2.3 GHz Intel Core i5, 8 GB RAM) with increasing inputs. Your score will be the greatest input that takes less than 1 minute to output the correct value.
Example
For example, the permutation [1, 2, 4, 3]
is minimally interpolable because
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 the illustration, you can see that the horizontal lines (red) have at most one point on them, the lines (blue) have at most two points on them, and the parabolas (green) have three points on them.
Data
Here are the minimally interpolable permutations for n=3
, n=4
, and 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]
If my program is correct, the first few values of a(n)
, the number of minimally interpolable permutations of {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
Nice sequence number! | Although you specified [tag:fastest-code], you didn't specify which machine is it fastest on. What is exactly the winning criteria? – user202729 – 2018-03-27T00:36:13.143
3To add to user202729's comment, I suggest some tags that you can use to determine the winning criteria: [tag:fastest-code] requires that submissions be tested on the same machine to compare the runtime (usually the OP of the challenge does this). [tag:fastest-algorithm] would ask answerers to come up with code with the lowest time complexity as possible. [tag:code-golf] would ask users to come up with code with the shortest source code (or equivalent) as possible. Other than that, this is indeed a nice challenge. – JungHwan Min – 2018-03-27T00:55:59.950
Your example text uses zero-indexing though the image uses one-indexing. – Jonathan Frech – 2018-03-27T20:54:19.783
Since all points are defined by permuations of the first natural numbers, is it not impossible for any two points to occupy the same height? – Jonathan Frech – 2018-03-27T20:57:14.153
@JonathanFrech, indeed, it should be 1-indexed because these are permutations. And you're correct! Because we're dealing with permutations, the 0-degree polynomial condition comes for free. – Peter Kagey – 2018-03-27T22:04:23.633
I confirm those eight terms. You could add the term a(0) = 1. For reference, how long does your program take to calculate a(8)? I'm at 11 seconds, and 144 seconds for a(9) = 10408. Now to start optimising... – Peter Taylor – 2018-03-28T08:46:51.937
My implementation takes 2.63 seconds to compute a(7) and 29.9 seconds to compute a(8). – Peter Kagey – 2018-03-28T19:15:58.780