Перестановки такие, что ни k + 2 точек не попадают ни в один полином степени k

16

Описание

Пусть перестановка целых чисел {1, 2, ..., n}будет называться минимально интерполируемой, если никакое множество k+2точек (вместе с их индексами) не попадает на многочлен степени k. То есть,

  1. Ни одна точка не падает на горизонтальную линию (полином 0 градусов)
  2. Ни одна точка не падает на линию (полином 1 степени)
  3. Никакие четыре точки не падают на параболу (полином 2 степени)
  4. И так далее.

Вызов

Напишите программу, которая вычисляет последовательность OEIS A301802 (n) , число минимально интерполируемых перестановок {1, 2, ..., n}для nкак можно большего числа.


счет

Я увеличу время ввода вашего кода на моем компьютере (2,3 ГГц Intel Core i5, 8 ГБ ОЗУ). Ваша оценка будет лучшим входом, который займет менее 1 минуты, чтобы вывести правильное значение.


пример

Например, перестановка [1, 2, 4, 3]минимально интерполируема, потому что

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.

Пример, иллюстрирующий, что [1,2,4,3] минимально интерполируется. На иллюстрации видно, что горизонтальные линии (красные) имеют не более одной точки, линии (синие) имеют не более двух точек, а параболы (зеленые) имеют три точки.


Данные

Вот минимально интерполяция перестановок для n=3, n=4и 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]

Если моя программа правильная, первые несколько значений a(n), количество минимально интерполируемых перестановок {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
Питер Кейджи
источник
Хороший порядковый номер! | Хотя вы указали самый быстрый код , вы не указали, на какой машине он работает быстрее всего. Каковы именно критерии победы?
user202729
3
Чтобы добавить к комментарию пользователя 202729, я предлагаю несколько тегов, которые вы можете использовать для определения критерия выигрыша: самый быстрый код требует, чтобы заявки тестировались на одной и той же машине для сравнения времени выполнения (обычно это делается в тесте). Алгоритм fasttest попросит ответчиков придумать код с наименьшей возможной сложностью по времени. code-golf попросит пользователей придумать код с максимально коротким исходным кодом (или эквивалентным), насколько это возможно. Помимо этого, это действительно хороший вызов.
JungHwan Мин
Ваш пример текста использует нулевую индексацию, хотя изображение использует одну индексацию.
Джонатан Фрех
Поскольку все точки определяются перестановками первых натуральных чисел, не является ли невозможным, чтобы любые две точки занимали одинаковую высоту?
Джонатан Фрех
@JonathanFrech, действительно, он должен быть 1-индексирован, потому что это перестановки. И ты прав! Поскольку мы имеем дело с перестановками, условие полинома 0 градусов приходит бесплатно.
Питер Кейджи

Ответы:

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

Принимает значения в nкачестве аргументов командной строки или, если выполняется без аргументов, время до самого n=10. Компиляция как "Release" в VS 2017 и запуск на Intel Core i7-6700 я вычисляю n=9за 1,2 секунды и n=10за 13,6 секунды. n=11чуть более 2 минут.

FWIW:

n    a(n)
9    10408
10   45244
11   160248
12   762554
Питер Тейлор
источник