Число возможных числовых результатов скобок 2 ^ 2 ^… ^ 2

19

Рассмотрим выражение 2^2^...^2с nоператорами ^. Оператор ^означает возведение в степень («во власть»). Предположим, что он не имеет ассоциативности по умолчанию, поэтому выражение должно быть заключено в круглые скобки, чтобы стать однозначным. Количество способов заключить выражение в скобки даны каталонскими числами C_n=(2n)!/(n+1)!/n! .

Иногда различные круглые скобки дают один и тот же числовой результат, например (2^2)^(2^2)=((2^2)^2)^2, поэтому число различных возможных числовых результатов для данного nменьше, чем C_nдля всех n>1. Последовательность начинается 1, 1, 2, 4, 8, ...в отличие от каталонских чисел1, 2, 5, 14, 42, ...

Проблема состоит в том, чтобы написать самую быструю программу (или функцию), которая принимает nв качестве входных данных и возвращает число различных возможных числовых результатов выражения 2^2^...^2с nоператорами ^. Производительность не должна значительно ухудшаться по мере nроста, поэтому прямой расчет мощных вышек, вероятно, является плохой идеей.

Владимир Решетников
источник
Я просто делюсь идеей здесь, но кажется, что должна быть возможность исключительно использовать сложение и умножение, так как ответ всегда будет иметь форму 2^n, и поэтому нет необходимости отслеживать что-либо кроме n. Т.е. просто использование правил возведения в степень кажется разумным. Тем не менее, безусловно, есть более умный и полностью алгебраический способ сделать это.
Форс
@ Я думаю, nон все еще слишком велик для вычислений. Тем не менее, хорошо отмечено. Может быть, рекурсивное представление в форме "1 или 2 ^ (...) или (...) + (...)"; но у вас все еще есть проблема, как нормализовать такое представление числа (или сравнить два представления для равенства значения).
Джон Дворжак
4
@JanDvorak, A002845 (закрытая форма не указана)
Питер Тейлор
3
Связанные oeis.org/A003018/a003018.pdf
Доктор Белизариус
1
@ Владимир Решетников: Я думаю, что в вашей формуле есть ошибка "один на один". Если у вас есть nдвойки и C_n=(2n)!/(n+1)!/n!должно быть количество скобок, то для n = 3 это должно быть 5, правильно? Я вижу (2^2)^2и 2^(2^2), но каковы другие три комбинации? Я думаю, что C_n дает вам количество скобок для n + 1 двойки.
Мартин Тома

Ответы:

9

Python 2.7

Этот подход использует следующие соображения:

Любое целое число может быть представлено как сумма степеней двух. Показатели в степени двух могут также быть представлены как степени двух. Например:

8 = 2^3 = 2^(2^1 + 2^0) = 2^(2^(2^0) + 2^0)

Эти выражения, которые мы заканчиваем, могут быть представлены как наборы множеств (в Python я использовал встроенный frozenset):

  • 0становится пустым набором {}.
  • 2^aстановится набором, содержащим набор, представляющий a. Например: 1 = 2^0 -> {{}}и 2 = 2^(2^0) -> {{{}}}.
  • a+bстановится объединением множеств, представляющих aи b. Например,3 = 2^(2^0) + 2^0 -> {{{}},{}}

Оказывается, что выражения формы 2^2^...^2можно легко преобразовать в их уникальное представление набора, даже когда числовое значение слишком велико, чтобы его можно было сохранить как целое число.


Для n=20, это работает в 8.7s на CPython 2.7.5 на моей машине (немного медленнее в Python 3 и намного медленнее в PyPy):

"""Analyze the expressions given by parenthesizations of 2^2^...^2.

Set representation:  s is a set of sets which represents an integer n.  n is
  given by the sum of all 2^m for the numbers m represented by the sets
  contained in s.  The empty set stands for the value 0.  Each number has
  exactly one set representation.

  In Python, frozensets are used for set representation.

  Definition in Python code:
      def numeric_value(s):
          n = sum(2**numeric_value(t) for t in s)
          return n"""

import itertools


def single_arg_memoize(func):
    """Fast memoization decorator for a function taking a single argument.

    The metadata of <func> is *not* preserved."""

    class Cache(dict):
        def __missing__(self, key):
            self[key] = result = func(key)
            return result
    return Cache().__getitem__


def count_results(num_exponentiations):
    """Return the number of results given by parenthesizations of 2^2^...^2."""
    return len(get_results(num_exponentiations))

@single_arg_memoize
def get_results(num_exponentiations):
    """Return a set of all results given by parenthesizations of 2^2^...^2.

    <num_exponentiations> is the number of exponentiation operators in the
    parenthesized expressions.

    The result of each parenthesized expression is given as a set.  The
    expression evaluates to 2^(2^n), where n is the number represented by the
    given set in set representation."""

    # The result of the expression "2" (0 exponentiations) is represented by
    # the empty set, since 2 = 2^(2^0).
    if num_exponentiations == 0:
        return {frozenset()}

    # Split the expression 2^2^...^2 at each of the first half of
    # exponentiation operators and parenthesize each side of the expession.
    split_points = xrange(num_exponentiations)
    splits = itertools.izip(split_points, reversed(split_points))
    splits_half = ((left_part, right_part) for left_part, right_part in splits
                                           if left_part <= right_part)

    results = set()
    results_add = results.add
    for left_part, right_part in splits_half:
        for left in get_results(left_part):
            for right in get_results(right_part):
                results_add(exponentiate(left, right))
                results_add(exponentiate(right, left))
    return results


def exponentiate(base, exponent):
    """Return the result of the exponentiation of <operands>.

    <operands> is a tuple of <base> and <exponent>.  The operators are each
    given as the set representation of n, where 2^(2^n) is the value the
    operator stands for.

    The return value is the set representation of r, where 2^(2^r) is the
    result of the exponentiation."""

    # Where b is the number represented by <base>, e is the number represented
    # by <exponent> and r is the number represented by the return value:
    #   2^(2^r) = (2^(2^b)) ^ (2^(2^e))
    #   2^(2^r) = 2^(2^b * 2^(2^e))
    #   2^(2^r) = 2^(2^(b + 2^e))
    #   r = b + 2^e

    # If <exponent> is not in <base>, insert it to arrive at the set with the
    # value: b + 2^e.  If <exponent> is already in <base>, take it out,
    # increment e by 1 and repeat from the start to eventually arrive at:
    #   b - 2^e + 2^(e+1) =
    #   b + 2^e
    while exponent in base:
        base -= {exponent}
        exponent = successor(exponent)
    return base | {exponent}

@single_arg_memoize
def successor(value):
    """Return the successor of <value> in set representation."""
    # Call exponentiate() with <value> as base and the empty set as exponent to
    # get the set representing (n being the number represented by <value>):
    #   n + 2^0
    #   n + 1
    return exponentiate(value, frozenset())


def main():
    import timeit
    print timeit.timeit(lambda: count_results(20), number=1)
    for i in xrange(21):
        print '{:.<2}..{:.>9}'.format(i, count_results(i))

if __name__ == '__main__':
    main()

(Концепция декоратора памятки скопирована с http://code.activestate.com/recipes/578231-probbly-the-fastest-memoization-decorator-in-the-/ .)

Выход:

8.667753234
0...........1
1...........1
2...........1
3...........2
4...........4
5...........8
6..........17
[...]
19.....688366
20....1619087

Сроки для разных n:

 n    time
16    0.240
17    0.592
18    1.426
19    3.559
20    8.668
21   21.402

Любое значение nвыше 21 приводит к ошибке памяти на моей машине.

Мне было бы интересно, если бы кто-нибудь мог сделать это быстрее, переведя это на другой язык.

Редактировать: Оптимизирована get_resultsфункция. Кроме того, использование Python 2.7.5 вместо 2.7.2 заставило его работать немного быстрее.

flornquake
источник
Я сделал перевод на C #, но использовал отсортированные массивы и выполнял сложение по порядку, а не по набору проверок. Это намного медленнее, и я еще не понял, связано ли это с тем, что не запомнил функцию-преемник или из-за стоимости сравнений.
Питер Тейлор
1
Я не профилировал (блестящий) код @ flornquake, но я бы предположил, что большая часть процессорного времени тратится на тестирование членства в наборе и операции манипуляции с наборами, которые довольно хорошо оптимизированы в Python, с использованием его вездесущей хеш-таблицы и хеш-ключа подпрограммы. Мемоизация, безусловно, важная вещь, с таким экспоненциальным алгоритмом, как этот. Если вы пропустили это, вы можете ожидать экспоненциально более низкой производительности.
Тобиа
@Tobia, на самом деле я обнаружил, что в C # запоминание функции-преемника делает его медленнее. Я также обнаружил, что более буквальный перевод (с использованием операций над множествами) был значительно медленнее, чем мое добавление более низкого уровня. Единственное реальное улучшение, которое я обнаружил по сравнению с моим исходным кодом, - это принять во внимание (a^b)^c = (a^c)^b, и оно все еще намного медленнее, чем эта реализация Python.
Питер Тейлор
@PeterTaylor: Edit: насколько я вижу, алгоритм flornquake основан на построении наборов деревьев, где дерево - это набор деревьев, и так далее. Все части этих деревьев, от самого маленького пустого набора до самого большого набора наборов, запоминаются. Это означает, что все эти деревья содержат «повторяющуюся структуру», которая вычисляется только один раз (процессором) и сохраняется один раз (в оперативной памяти). Вы уверены, что ваш алгоритм «сложения по порядку» идентифицирует всю эту повторяющуюся структуру и вычисляет ее один раз? (то, что я назвал выше экспоненциальной сложностью). См. также en.wikipedia.org/wiki/Dynamic_programming
Tobia
@ Тобия, мы пересеклись. Я отправил код.
Питер Тейлор
5

C #

Это перевод кода Python flornquake на C # с использованием процедуры добавления более низкого уровня, которая обеспечивает умеренное ускорение по сравнению с прямым переводом. Это не самая оптимизированная версия, которая у меня есть, но она немного длиннее, потому что она должна хранить как древовидную структуру, так и значения.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox {
    class PowerTowers {
        public static void Main() {
            DateTime start = DateTime.UtcNow;
            for (int i = 0; i < 17; i++)
                Console.WriteLine("{2}: {0} (in {1})", Results(i).Count, DateTime.UtcNow - start, i);
        }

        private static IList<HashSet<Number>> _MemoisedResults;

        static HashSet<Number> Results(int numExponentations) {
            if (_MemoisedResults == null) {
                _MemoisedResults = new List<HashSet<Number>>();
                _MemoisedResults.Add(new HashSet<Number>(new Number[] { Number.Zero }));
            }

            if (numExponentations < _MemoisedResults.Count) return _MemoisedResults[numExponentations];

            HashSet<Number> rv = new HashSet<Number>();
            for (int i = 0; i < numExponentations; i++) {
                IEnumerable<Number> rhs = Results(numExponentations - 1 - i);
                foreach (var b in Results(i))
                    foreach (var e in rhs) {
                        if (!e.Equals(Number.One)) rv.Add(b.Add(e.Exp2()));
                    }
            }
            _MemoisedResults.Add(rv);
            return rv;
        }
    }

    // Immutable
    struct Number : IComparable<Number> {
        public static Number Zero = new Number(new Number[0]);
        public static Number One = new Number(Zero);

        // Ascending order
        private readonly Number[] _Children;
        private readonly int _Depth;
        private readonly int _HashCode;

        private Number(params Number[] children) {
            _Children = children;
            _Depth = children.Length == 0 ? 0 : 1 + children[children.Length - 1]._Depth;

            int hashCode = 0;
            foreach (var n in _Children) hashCode = hashCode * 37 + n.GetHashCode() + 1;
            _HashCode = hashCode;
        }

        public Number Add(Number n) {
            // "Standard" bitwise adder built from full adder.
            // Work forwards because children are in ascending order.
            int off1 = 0, off2 = 0;
            IList<Number> result = new List<Number>();
            Number? carry = default(Number?);

            while (true) {
                if (!carry.HasValue) {
                    // Simple case
                    if (off1 < _Children.Length) {
                        if (off2 < n._Children.Length) {
                            int cmp = _Children[off1].CompareTo(n._Children[off2]);
                            if (cmp < 0) result.Add(_Children[off1++]);
                            else if (cmp == 0) {
                                carry = _Children[off1++].Add(One);
                                off2++;
                            }
                            else result.Add(n._Children[off2++]);
                        }
                        else result.Add(_Children[off1++]);
                    }
                    else if (off2 < n._Children.Length) result.Add(n._Children[off2++]);
                    else return new Number(result.ToArray()); // nothing left to add
                }
                else {
                    // carry is the (possibly joint) smallest value
                    int matches = 0;
                    if (off1 < _Children.Length && carry.Value.Equals(_Children[off1])) {
                        matches++;
                        off1++;
                    }
                    if (off2 < n._Children.Length && carry.Value.Equals(n._Children[off2])) {
                        matches++;
                        off2++;
                    }

                    if ((matches & 1) == 0) result.Add(carry.Value);
                    carry = matches == 0 ? default(Number?) : carry.Value.Add(One);
                }
            }
        }

        public Number Exp2() {
            return new Number(this);
        }

        public int CompareTo(Number other) {
            if (_Depth != other._Depth) return _Depth.CompareTo(other._Depth);

            // Work backwards because children are in ascending order
            int off1 = _Children.Length - 1, off2 = other._Children.Length - 1;
            while (off1 >= 0 && off2 >= 0) {
                int cmp = _Children[off1--].CompareTo(other._Children[off2--]);
                if (cmp != 0) return cmp;
            }

            return off1.CompareTo(off2);
        }

        public override bool Equals(object obj) {
            if (!(obj is Number)) return false;

            Number n = (Number)obj;
            if (n._HashCode != _HashCode || n._Depth != _Depth || n._Children.Length != _Children.Length) return false;
            for (int i = 0; i < _Children.Length; i++) {
                if (!_Children[i].Equals(n._Children[i])) return false;
            }

            return true;
        }

        public override int GetHashCode() {
            return _HashCode;
        }
    }
}
Питер Тейлор
источник