Deskripsi
Biarkan permutasi bilangan bulat {1, 2, ..., n}
disebut interpolable minimal jika tidak ada set k+2
poin (bersama dengan indeksnya) jatuh pada polinomial derajat k
. Itu adalah,
- Tidak ada dua titik yang jatuh pada garis horizontal (polinomial 0 derajat)
- Tidak ada tiga poin yang jatuh pada garis (polinomial 1 derajat)
- Tidak ada empat poin yang jatuh pada parabola (polinomial 2 derajat)
- Dll.
Tantangan
Tulis sebuah program yang menghitung urutan OEIS A301802 (n) , jumlah permutasi yang dapat interpolable minimal {1, 2, ..., n}
untuk n
sebesar mungkin.
Mencetak gol
Saya akan mengatur waktu kode Anda di komputer saya (2,3 GHz Intel Core i5, 8 GB RAM) dengan input yang meningkat. Skor Anda akan menjadi input terbesar yang membutuhkan waktu kurang dari 1 menit untuk menghasilkan nilai yang benar.
Contoh
Sebagai contoh, permutasi [1, 2, 4, 3]
adalah interpolable minimal karena
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.
Dalam ilustrasi, Anda dapat melihat bahwa garis horizontal (merah) memiliki paling banyak satu titik pada mereka, garis (biru) memiliki paling banyak dua titik pada mereka, dan parabola (hijau) memiliki tiga titik pada mereka.
Data
Berikut adalah permutasi minimal interpolable untuk n=3
, n=4
, dan 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]
Jika program saya benar, beberapa nilai pertama a(n)
, jumlah permutasi minimal yang dapat diinterpolasi dari {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
sumber
Jawaban:
C #
Mengambil nilai-nilai
n
sebagai argumen baris perintah, atau jika dijalankan tanpa argumen, waktu akan naikn=10
. Kompilasi sebagai "Rilis" di VS 2017 dan berjalan pada Intel Core i7-6700 saya menghitungn=9
dalam 1,2 detik, dann=10
dalam 13,6 detik.n=11
hanya lebih dari 2 menit.FWIW:
sumber