Opis

Niech permutacja liczb całkowitych {1, 2, ..., n}będzie nazywana minimalnie interpolowalną, jeśli żaden zestaw k+2punktów (wraz z ich indeksami) nie spadnie na wielomian stopnia k. To jest,

1. Żadne dwa punkty nie spadają na linię poziomą (wielomian 0 stopni)
2. Żadne trzy punkty nie spadają na linię (wielomian 1 stopnia)
3. Żadne cztery punkty nie spadają na parabolę (wielomian 2-stopniowy)
4. I tak dalej.

Wyzwanie

Napisz program, który oblicza sekwencję OEIS A301802 (n) , liczbę permutacji minimalnie interpolowanych {1, 2, ..., n}dla njak 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=4i 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

DO#

using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 13; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];

            // Symmetry exclusion: perm[0] < (n+1) / 2
            if (n > 1) excluded[0] = (1 << n) - (1 << ((n + 1) / 2));

            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            int n = perm.Length;
            if (off == n)
            {
                count += CountSymmetries(perm);
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < n; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < n - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                // Symmetry exclusion: perm[0] < perm[-1] < n - 1 - perm[0]
                if (off == 0 && n > 1)
                {
                    nextExcluded[n - 1] |= (1 << n) - (2 << (n - 1 - val));
                    nextExcluded[n - 1] |= (2 << val) - 1;
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        private static int CountSymmetries(int[] perm)
        {
            if (perm.Length < 2) return 1;

            int cmp = 0;
            for (int i = 0, j = perm.Length - 1; i <= j; i++, j--)
            {
                cmp = perm.Length - 1 - perm[i] - perm[j];
                if (cmp != 0) break;
            }

            return cmp > 0 ? 4 : cmp == 0 ? 2 : 0;
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Pobiera wartości njako argumenty wiersza polecenia lub jeśli uruchamia się bez argumentów razy do siebie n=10. Kompilując jako „Release” w VS 2017 i działając na Intel Core i7-6700, obliczam n=9w 1,2 sekundy, a n=10w 13,6 sekundy. n=11to nieco ponad 2 minuty.

FWIW:

n    a(n)
9    10408
10   45244
11   160248
12   762554