Permutations telles qu'aucun k + 2 points ne tombe sur un polynôme de degré k

16

La description

Supposons qu'une permutation des nombres entiers {1, 2, ..., n}soit appelée à interpolation minimale si aucun ensemble de k+2points (avec leurs indices) ne tombe sur un polynôme de degré k. C'est,

  1. Aucun point ne tombe sur une ligne horizontale (polynôme à 0 degré)
  2. Aucun point ne tombe sur une ligne (polynôme à 1 degré)
  3. Pas quatre points tombent sur une parabole (polynôme à 2 degrés)
  4. Etc.

Défi

Écrivez un programme qui calcule la séquence OEIS A301802 (n) , le nombre de permutations minimalement interpolables {1, 2, ..., n}pour naussi grand que possible.


Notation

Je chronométrerai votre code sur mon ordinateur (Intel Core i5 2,3 GHz, 8 Go de RAM) avec des entrées croissantes. Votre score sera la meilleure entrée qui prendra moins de 1 minute pour sortir la valeur correcte.


Exemple

Par exemple, la permutation [1, 2, 4, 3]est interpolable de façon minimale car

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.

Exemple illustrant que [1,2,4,3] est interpolable de façon minimale. Dans l'illustration, vous pouvez voir que les lignes horizontales (rouges) ont au plus un point sur elles, les lignes (bleues) ont au plus deux points sur elles et les paraboles (vertes) ont trois points sur elles.


Les données

Voici les permutations peu interpolables pour n=3, n=4et 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]

Si mon programme est correct, les premières valeurs de a(n), le nombre de permutations minimalement interpolables de {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
la source
Joli numéro de séquence! | Bien que vous ayez spécifié le code le plus rapide , vous n'avez pas spécifié sur quelle machine il est le plus rapide. Quels sont exactement les critères gagnants?
user202729
3
Pour ajouter au commentaire de user202729, je suggère quelques balises que vous pouvez utiliser pour déterminer les critères gagnants: le code le plus rapide nécessite que les soumissions soient testées sur la même machine pour comparer le temps d'exécution (généralement l'OP du défi fait cela). l'algorithme le plus rapide demanderait aux répondeurs de trouver du code avec la complexité temporelle la plus faible possible. code-golf demanderait aux utilisateurs de trouver le code avec le code source le plus court (ou équivalent) possible. En dehors de cela, c'est en effet un beau défi.
JungHwan Min
Votre exemple de texte utilise l'indexation zéro bien que l'image utilise une indexation unique.
Jonathan Frech
Puisque tous les points sont définis par des permations des premiers nombres naturels, n'est-il pas impossible que deux points occupent la même hauteur?
Jonathan Frech
@JonathanFrech, en effet, il devrait être indexé 1 car ce sont des permutations. Et tu as raison! Parce que nous avons affaire à des permutations, la condition polynomiale à 0 degré est gratuite.
Peter Kagey

Réponses:

5

C #

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);
        }
    }
}

Prend des valeurs en ntant qu'arguments de ligne de commande, ou s'il est exécuté sans arguments, il se multiplie jusqu'à n=10. Compiler comme "Release" dans VS 2017 et fonctionner sur un Intel Core i7-6700 je calcule n=9en 1,2 seconde et n=10en 13,6 secondes. n=11est un peu plus de 2 minutes.

FWIW:

n    a(n)
9    10408
10   45244
11   160248
12   762554
Peter Taylor
la source