Die Anzahl der möglichen numerischen Ergebnisse von Klammern von 2 ^ 2 ^… ^ 2

19

Betrachten Sie einen Ausdruck 2^2^...^2mit nOperatoren ^. Operator ^bedeutet Potenzierung ("hoch"). Angenommen, es gibt keine Standardassoziativität, sodass der Ausdruck vollständig in Klammern gesetzt werden muss, um eindeutig zu werden. Die Anzahl der Möglichkeiten, den Ausdruck in Klammern zu setzen, wird durch katalanische Zahlen angegeben C_n=(2n)!/(n+1)!/n! .

Manchmal führen unterschiedliche Klammern beispielsweise zu demselben numerischen Ergebnis, (2^2)^(2^2)=((2^2)^2)^2sodass die Anzahl der unterschiedlichen möglichen numerischen Ergebnisse für eine bestimmte Zahl ngeringer ist als C_nfür alle anderen n>1. Die Sequenz beginnt 1, 1, 2, 4, 8, ...im Gegensatz zu katalanischen Zahlen1, 2, 5, 14, 42, ...

Das Problem besteht darin, das schnellste Programm (oder die schnellste Funktion) zu schreiben, das bzw. die nals Eingabe akzeptiert und die Anzahl der verschiedenen möglichen numerischen Ergebnisse des Ausdrucks 2^2^...^2mit nOperatoren zurückgibt ^. Die Leistung sollte sich mit zunehmender Leistung nicht wesentlich verschlechtern n, daher ist die direkte Berechnung von Hochleistungstürmen wahrscheinlich eine schlechte Idee.

Vladimir Reshetnikov
quelle
Ich teile hier nur eine Idee, aber es scheint, dass es möglich sein sollte, ausschließlich Addition und Multiplikation zu verwenden, da die Antwort immer von der Form sein 2^nwird und es daher unnötig wäre, alles außer zu verfolgen n. Das heißt, nur die Regeln der Potenzierung zu verwenden, scheint klug. Es gibt jedoch sicherlich eine intelligentere und vollständig algebraische Möglichkeit, dies zu tun.
Fors
@Für mich nist das wohl noch viel zu groß zum rechnen. Trotzdem gut bemerkt. Möglicherweise eine rekursive Darstellung in der Form "1 oder 2 ^ (...) oder (...) + (...)"; Sie haben jedoch immer noch das Problem, wie Sie eine solche Darstellung einer Zahl normalisieren (oder zwei Darstellungen auf Wertgleichheit vergleichen).
John Dvorak
4
@ JanDvorak, A002845 (keine geschlossene Form angegeben)
Peter Taylor
3
Related oeis.org/A003018/a003018.pdf
Dr. belisarius
1
@Vladimir Reshetnikov: Ich denke, es gibt einen Fehler in Ihrer Formel. Wenn Sie nzwei haben und C_n=(2n)!/(n+1)!/n!die Anzahl der Klammern sein sollten, dann sollte es für n = 3 5 sein, richtig? Ich sehe (2^2)^2und 2^(2^2), aber was sind die anderen drei Kombinationen? Ich denke, C_n gibt Ihnen die Anzahl der Klammern für n + 1 Zweien.
Martin Thoma

Antworten:

9

Python 2.7

Dieser Ansatz nutzt die folgenden Überlegungen:

Jede ganze Zahl kann als Summe von Zweierpotenzen dargestellt werden. Die Exponenten in Zweierpotenzen können auch als Zweierpotenzen dargestellt werden. Beispielsweise:

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

Diese Ausdrücke, mit denen wir enden, können als Mengen von Mengen dargestellt werden (in Python habe ich die eingebauten verwendet frozenset):

  • 0wird die leere Menge {}.
  • 2^awird die Menge, die die Menge darstellt a. ZB: 1 = 2^0 -> {{}}und 2 = 2^(2^0) -> {{{}}}.
  • a+bwird zur Verkettung der Mengen, die aund darstellen b. Z.B,3 = 2^(2^0) + 2^0 -> {{{}},{}}

Es stellt sich heraus, dass Ausdrücke des Formulars 2^2^...^2leicht in ihre eindeutige Mengenrepräsentation umgewandelt werden können, selbst wenn der numerische Wert viel zu groß ist, um als Ganzzahl gespeichert zu werden.


Für n=20läuft dies in 8.7s auf CPython 2.7.5 auf meinem Computer (etwas langsamer in Python 3 und viel langsamer in 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()

(Das Konzept des Memoization Decorators wurde von http://code.activestate.com/recipes/578231-wahrscheinlich-der-schnellste-Memoization-Decorator-in- / kopiert .)

Ausgabe:

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

Timings für verschiedene n:

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

Jegliche nüber 21 führt zu einem Speicherfehler auf meinem Rechner.

Es würde mich interessieren, ob jemand dies beschleunigen kann, indem er es in eine andere Sprache übersetzt.

Bearbeiten:get_results Funktion optimiert . Die Verwendung von Python 2.7.5 anstelle von 2.7.2 beschleunigte zudem die Ausführung.

Flornbeben
quelle
Ich habe eine C # -Übersetzung durchgeführt, aber ich habe sortierte Arrays verwendet und die Addition in der Reihenfolge ausgeführt, in der sie nicht als Set enthalten ist. Es ist viel langsamer, und ich habe noch kein Profil erstellt, um festzustellen, ob dies daran liegt, dass ich die Nachfolgerfunktion nicht auswendig gelernt habe oder an den Kosten für Vergleiche.
Peter Taylor
1
Ich habe @ flornquakes (brillanten) Code nicht profiliert, aber ich gehe davon aus, dass ein Großteil der CPU-Zeit für Set-Membership-Tests und Set-Manipulationsoperationen aufgewendet wird, die beide in Python unter Verwendung der allgegenwärtigen Hash-Tabelle und des Hash-Schlüssels ziemlich gut optimiert sind Routinen. Mit einem exponentiellen Algorithmus wie diesem ist das Auswendiglernen mit Sicherheit eine große Sache. Wenn Sie dies weglassen, können Sie mit einer exponentiell geringeren Leistung rechnen.
Tobia
@Tobia, eigentlich habe ich festgestellt, dass in C # das Auswendiglernen der Nachfolgerfunktion langsamer gemacht wird. Ich stellte auch fest, dass eine wörtlichere Übersetzung (unter Verwendung von Mengenoperationen) erheblich langsamer war als meine Addition auf niedrigerer Ebene. Die einzige echte Verbesserung, die ich gegenüber meinem ursprünglichen Code gefunden habe, war die Berücksichtigung (a^b)^c = (a^c)^b, und sie ist immer noch viel langsamer als diese Python-Implementierung.
Peter Taylor
@ PeterTaylor: Bearbeiten: Soweit ich sehen kann, basiert der Algorithmus von Flornquake auf dem Bauen von Baumgruppen, wobei ein Baum selbst eine Baumgruppe ist, und so weiter. Alle Teile dieser Bäume, vom kleinsten leeren Satz bis zum größten Satz von Sätzen, werden auswendig gelernt. Dies bedeutet, dass alle diese Bäume eine "wiederholte Struktur" enthalten, die nur einmal (von der CPU) berechnet und einmal (im RAM) gespeichert wird. Sind Sie sicher, dass Ihr Algorithmus "Addition in Reihenfolge" all diese wiederholten Strukturen identifiziert und einmal berechnet? (was ich oben als exponentielle Komplexität bezeichnet habe) Siehe auch en.wikipedia.org/wiki/Dynamic_programming
Tobia
@Tobia, wir haben uns überlappt. Ich habe den Code gepostet.
Peter Taylor
5

C #

Dies ist eine Übersetzung von Flornquakes Python-Code in C # unter Verwendung einer Additionsroutine auf niedrigerer Ebene, die eine moderate Beschleunigung gegenüber einer direkten Übersetzung bietet. Es ist nicht die optimierteste Version, die ich habe, aber das ist ziemlich viel länger, da es die Baumstruktur sowie die Werte speichern muss.

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
quelle