Permutacje takie, że żadne k + 2 punkty nie spadają na żaden wielomian stopnia k

16

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.

Przykład ilustrujący, że [1,2,4,3] jest minimalnie interpolowany. 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
Peter Kagey
źródło
Niezły numer porządkowy! | Chociaż podałeś najszybszy kod , nie określiłeś, na której maszynie jest on najszybszy. Jakie są dokładnie zwycięskie kryteria?
user202729
3
Aby dodać do komentarza user202729, sugeruję kilka tagów, których można użyć do ustalenia kryteriów zwycięstwa: najszybszy kod wymaga przetestowania zgłoszeń na tej samej maszynie w celu porównania środowiska wykonawczego (zazwyczaj robi to OP wyzwania). Najszybszy algorytm poprosiłby autorów o wymyślenie kodu o możliwie najniższej złożoności czasowej. code-golf poprosiłby użytkowników o wymyślenie kodu z możliwie najkrótszym kodem źródłowym (lub równoważnym). Poza tym jest to naprawdę miłe wyzwanie.
JungHwan Min
Twój przykładowy tekst wykorzystuje indeksowanie zerowe, chociaż obraz używa indeksowania jednokrotnego.
Jonathan Frech
Ponieważ wszystkie punkty są zdefiniowane przez permuacje pierwszych liczb naturalnych, czy nie jest niemożliwe, aby jakieś dwa punkty zajmowały tę samą wysokość?
Jonathan Frech
@JathanathanFrech rzeczywiście powinien być indeksowany 1, ponieważ są to permutacje. I masz rację! Ponieważ mamy do czynienia z permutacjami, warunek wielomianu 0 stopni jest darmowy.
Peter Kagey

Odpowiedzi:

5

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
Peter Taylor
źródło