Liczba możliwych wyników liczbowych nawiasów 2 ^ 2 ^… ^ 2

19

Rozważ wyrażenie 2^2^...^2z noperatorami ^. Operator ^oznacza potęgowanie („do potęgi”). Załóżmy, że nie ma domyślnej asocjatywności, więc wyrażenie musi być całkowicie nawiasowane, aby stało się jednoznaczne. Liczbę sposobów nawiasowania wyrażenia podano w liczbach katalońskich C_n=(2n)!/(n+1)!/n! .

Czasami różne nawiasy dają na przykład ten sam wynik liczbowy (2^2)^(2^2)=((2^2)^2)^2, więc liczba różnych możliwych wyników liczbowych dla danej njest mniejsza niż C_ndla wszystkich n>1. Sekwencja zaczyna się 1, 1, 2, 4, 8, ...w przeciwieństwie do liczb katalońskich1, 2, 5, 14, 42, ...

Problem polega na tym, aby napisać najszybszy program (lub funkcja), która przyjmuje njako dane wejściowe i zwraca liczbę różnych możliwych wyników liczbowych wyrażenia 2^2^...^2z noperatorami ^. Wydajność nie powinna ulec znacznemu pogorszeniu w miarę nwzrostu, więc bezpośrednie obliczenie wież dużej mocy jest prawdopodobnie złym pomysłem.

Vladimir Reshetnikov
źródło
Po prostu dzielę się tutaj pomysłem, ale wydaje się, że powinno być możliwe stosowanie wyłącznie dodawania i mnożenia, ponieważ odpowiedź zawsze będzie miała formę 2^n, a zatem śledzenie czegokolwiek byłoby zbędne n. Tj. Samo stosowanie reguł potęgowania wydaje się rozsądne. Jednak z pewnością jest to mądrzejszy i całkowicie algebraiczny sposób.
Fors
@Fors wydaje mi się, że njest wciąż zbyt duży, by go obliczyć. Nadal dobrze zauważone. Być może rekurencyjna reprezentacja w postaci „1 lub 2 ^ (...) lub (...) + (...)”; ale nadal masz problem ze znormalizowaniem takiej reprezentacji liczby (lub porównać dwie reprezentacje dla równości wartości).
John Dvorak,
4
@JanDvorak, A002845 (bez formularza zamkniętego)
Peter Taylor
3
Powiązane oeis.org/A003018/a003018.pdf
Dr. belisarius
1
@Vladimir Reshetnikov: Myślę, że w twojej formule występuje błąd „jeden po drugim”. Jeśli masz ndwie pary i C_n=(2n)!/(n+1)!/n!powinna być liczba nawiasów, to dla n = 3 powinno to być 5, prawda? Rozumiem (2^2)^2i 2^(2^2), ale jakie są pozostałe trzy kombinacje? Myślę, że C_n podaje liczbę nawiasów dla n + 1 dwójki.
Martin Thoma,

Odpowiedzi:

9

Python 2.7

Podejście to wykorzystuje następujące uwagi:

Każda liczba całkowita może być reprezentowana jako suma potęg dwóch. Potęgi potęg dwójki można również przedstawić jako potęgi dwójki. Na przykład:

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

Te wyrażenia, z którymi się skończyliśmy, mogą być reprezentowane jako zestawy zestawów (w Pythonie użyłem wbudowanego frozenset):

  • 0staje się pustym zestawem {}.
  • 2^astaje się zbiorem zawierającym zbiór reprezentujący a. Np .: 1 = 2^0 -> {{}}i 2 = 2^(2^0) -> {{{}}}.
  • a+bstaje się konkatenacją zbiorów reprezentujących ai b. Na przykład,3 = 2^(2^0) + 2^0 -> {{{}},{}}

Okazuje się, że wyrażenia formularza 2^2^...^2można łatwo przekształcić w ich unikatową reprezentację zestawu, nawet gdy wartość liczbowa jest zbyt duża, aby można ją było zapisać jako liczbę całkowitą.


Ponieważ n=20działa to w 8.7s na CPython 2.7.5 na moim komputerze (nieco wolniej w Pythonie 3 i znacznie wolniej w 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()

(Koncepcja dekoratora notatek została skopiowana z http://code.activestate.com/recipes/578231- prawdopodobnie-the-fastest-memoization-decorator-in-the-/ .)

Wynik:

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

Czasy dla różnych n:

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

Każda npowyżej 21 powoduje błąd pamięci na moim komputerze.

Byłbym zainteresowany, gdyby ktokolwiek mógł to przyspieszyć, tłumacząc go na inny język.

Edycja: Zoptymalizowana get_resultsfunkcja. Ponadto użycie Python 2.7.5 zamiast 2.7.2 sprawiło, że działał on nieco szybciej.

trzęsienie ziemi
źródło
Zrobiłem tłumaczenie C #, ale używając posortowanych tablic i dodając je w kolejności, a nie według zestawu zawiera kontrole. Jest o wiele wolniejszy i jeszcze nie profilowałem, aby zobaczyć, czy wynika to z braku zapamiętywania funkcji następcy, czy z powodu kosztów porównań.
Peter Taylor,
1
Nie profilowałem (świetnego) kodu @ flornquake, ale zakładam, że większość czasu procesora jest poświęcana na ustawianie testów członkostwa i ustawianie operacji manipulacji, które są dość dobrze zoptymalizowane w Pythonie, przy użyciu jego wszechobecnej tabeli mieszającej i klucza mieszającego rutyny. Zapamiętywanie jest z pewnością dużą rzeczą, z takim algorytmem wykładniczym. Jeśli to pominąłeś, możesz spodziewać się wykładniczo wolniejszej wydajności.
Tobia
@Tobia, faktycznie odkryłem, że w C # zapamiętanie funkcji następcy spowolniło. Odkryłem również, że bardziej dosłowne tłumaczenie (przy użyciu operacji ustawiania) było znacznie wolniejsze niż moje dodawanie niższego poziomu. Jedynym prawdziwym usprawnieniem, jakie znalazłem w stosunku do mojego oryginalnego kodu, było wzięcie pod uwagę (a^b)^c = (a^c)^b, i nadal jest ono znacznie wolniejsze niż ta implementacja Pythona.
Peter Taylor
@PeterTaylor: Edycja: Z tego, co widzę, algorytm flornquake opiera się na budowaniu zestawów drzew, gdzie drzewo jest zestawem samych drzew i tak dalej. Wszystkie elementy tych drzew, od najmniejszego pustego zestawu do największego zestawu zestawów, są zapamiętywane. Oznacza to, że wszystkie te drzewa zawierają „powtarzalną strukturę”, która jest obliczana tylko raz (przez CPU) i przechowywana raz (w pamięci RAM). Czy jesteś pewien, że Twój algorytm „dodawania w kolejności” identyfikuje całą tę powtarzającą się strukturę i oblicza ją raz? (co powyżej nazwałem złożonością wykładniczą) Zobacz także: en.wikipedia.org/wiki/Dynamic_programming
Tobia
@Tobia, pokryliśmy się. Opublikowałem kod.
Peter Taylor
5

DO#

Jest to tłumaczenie kodu Python flornquake'a na język C # przy użyciu procedury dodawania niższego poziomu, która zapewnia umiarkowane przyspieszenie w stosunku do tłumaczenia bezpośredniego. To nie jest najbardziej zoptymalizowana wersja, jaką mam, ale to trochę dłużej, ponieważ musi przechowywać zarówno strukturę drzewa, jak i wartości.

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