Jumlah kemungkinan hasil numerik kurung 2 ^ 2 ^ ... ^ 2

19

Pertimbangkan ekspresi 2^2^...^2dengan noperator ^. Operator ^berarti eksponensial ("dengan kekuatan"). Asumsikan bahwa ia tidak memiliki asosiatif default, sehingga ekspresi perlu dikurung sepenuhnya untuk menjadi tidak ambigu. Jumlah cara untuk mengurung ekspresi diberikan oleh angka Catalan C_n=(2n)!/(n+1)!/n! .

Kadang-kadang tanda kurung yang berbeda memberikan hasil numerik yang sama, misalnya (2^2)^(2^2)=((2^2)^2)^2, sehingga jumlah kemungkinan hasil numerik yang berbeda untuk yang diberikan nlebih sedikit daripada C_nuntuk semua n>1. Urutan dimulai 1, 1, 2, 4, 8, ...sebagai kebalikan dari angka Catalan1, 2, 5, 14, 42, ...

Masalahnya adalah untuk menulis program (atau fungsi) tercepat yang menerima nsebagai input dan mengembalikan jumlah hasil numerik yang berbeda dari ekspresi 2^2^...^2dengan noperator ^. Kinerja tidak boleh memburuk secara signifikan seiring npertumbuhan, jadi perhitungan langsung menara daya tinggi mungkin merupakan ide yang buruk.

Vladimir Reshetnikov
sumber
Saya hanya berbagi ide di sini, tetapi tampaknya mungkin untuk secara eksklusif menggunakan penjumlahan dan perkalian, karena jawabannya akan selalu dalam bentuk 2^n, dan karena itu tidak perlu untuk melacak apa pun kecuali n. Yaitu, hanya menggunakan aturan eksponensial tampaknya bijaksana. Namun, pasti ada cara yang lebih cerdas dan sepenuhnya aljabar untuk melakukan ini.
Fors
@Fors Saya kira nini masih terlalu besar untuk menghitung. Masih, dicatat dengan baik. Mungkin representasi rekursif dalam bentuk "1 atau 2 ^ (...) atau (...) + (...)"; tetapi Anda masih memiliki masalah tentang cara menormalkan representasi nomor tersebut (atau membandingkan dua representasi untuk kesetaraan nilai).
John Dvorak
4
@JanDvorak, A002845 (tidak ada formulir tertutup yang diberikan)
Peter Taylor
3
Terkait oeis.org/A003018/a003018.pdf
Dr. belisarius
1
@Vladimir Reshetnikov: Saya pikir ada kesalahan satu-per-satu dalam rumus Anda. Ketika Anda memiliki ndua pasangan dan C_n=(2n)!/(n+1)!/n!harus menjadi jumlah tanda kurung, maka untuk n = 3 itu harus 5, benar? Saya melihat (2^2)^2dan 2^(2^2), tetapi apakah tiga kombinasi lainnya? Saya pikir C_n memberi Anda jumlah tanda kurung untuk n + 1 dua.
Martin Thoma

Jawaban:

9

Python 2.7

Pendekatan ini mengambil keuntungan dari pertimbangan berikut:

Setiap bilangan bulat dapat direpresentasikan sebagai jumlah dari kekuatan dua. Eksponen dalam kekuatan dua juga dapat direpresentasikan sebagai kekuatan dua. Sebagai contoh:

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

Ekspresi ini yang kita hasilkan dapat direpresentasikan sebagai set set (dengan Python, saya menggunakan built-in frozenset):

  • 0menjadi set kosong {}.
  • 2^amenjadi himpunan yang berisi himpunan yang mewakili a. Misalnya: 1 = 2^0 -> {{}}dan 2 = 2^(2^0) -> {{{}}}.
  • a+bmenjadi gabungan dari set yang mewakili adan b. Misalnya,3 = 2^(2^0) + 2^0 -> {{{}},{}}

Ternyata ekspresi formulir 2^2^...^2dapat dengan mudah diubah menjadi representasi himpunan unik mereka, bahkan ketika nilai numeriknya terlalu besar untuk disimpan sebagai integer.


Sebab n=20, ini berjalan dalam 8.7s pada CPython 2.7.5 di komputer saya (sedikit lebih lambat di Python 3 dan jauh lebih lambat di 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()

(Konsep dekorator memoisasi disalin dari http://code.activestate.com/recipes/578231-probably-the-fastest-memoization-decorator-in-the-/ .)

Keluaran:

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

Pengaturan waktu untuk berbeda n:

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

Setiap n21 di atas menghasilkan kesalahan memori pada mesin saya.

Saya tertarik jika ada yang bisa membuat ini lebih cepat dengan menerjemahkannya ke bahasa yang berbeda.

Sunting: Mengoptimalkan get_resultsfungsi. Juga, menggunakan Python 2.7.5 bukannya 2.7.2 membuatnya berjalan sedikit lebih cepat.

gempa bumi
sumber
Saya membuat terjemahan C # tetapi menggunakan array yang diurutkan dan melakukan penambahan secara berurutan daripada set berisi cek. Ini jauh lebih lambat, dan saya belum memprofilkan untuk melihat apakah itu karena tidak memoising fungsi penggantinya atau karena biaya perbandingan.
Peter Taylor
1
Saya belum memprofilkan kode @ flornquake (brilian), tetapi saya berasumsi banyak waktu CPU dihabiskan untuk melakukan tes keanggotaan dan mengatur operasi manipulasi, yang keduanya dioptimalkan dengan cukup baik dengan Python, menggunakan tabel hash dan kunci hash di mana-mana. rutinitas. Memoisasi tentu merupakan hal besar, dengan algoritma eksponensial seperti ini. Jika Anda mengabaikannya, Anda dapat mengharapkan kinerja yang lebih lambat secara eksponensial.
Tobia
@Tobia, sebenarnya saya menemukan bahwa di C # memoising fungsi penerus membuatnya lebih lambat. Saya juga menemukan bahwa terjemahan yang lebih literal (menggunakan operasi yang ditetapkan) secara signifikan lebih lambat daripada penambahan level saya yang lebih rendah. Satu-satunya perbaikan nyata yang saya temukan di atas kode asli saya adalah untuk memperhitungkan (a^b)^c = (a^c)^b, dan itu masih jauh lebih lambat daripada implementasi Python ini.
Peter Taylor
@PeterTaylor: Edit: Sejauh yang saya bisa lihat, algoritma flornquake bergantung pada set bangunan pohon, di mana pohon adalah set pohon itu sendiri, dan sebagainya. Semua potongan pohon ini, dari set kosong terkecil hingga set set terbesar, disimpan dalam memo. Ini berarti bahwa semua pohon ini mengandung "struktur berulang" yang hanya dihitung sekali (oleh CPU) dan disimpan sekali (dalam RAM). Apakah Anda yakin bahwa algoritme "penambahan dalam urutan" Anda mengidentifikasi semua struktur berulang ini dan menghitungnya sekali? (Apa yang saya sebut kompleksitas eksponensial di atas) Lihat juga en.wikipedia.org/wiki/Dynamic_programming
Tobia
@Tobia, kami tumpang tindih. Saya sudah memposting kode.
Peter Taylor
5

C #

Ini adalah terjemahan kode Python flornquake ke C # menggunakan rutin tambahan tingkat rendah yang memberikan peningkatan kecepatan melalui terjemahan langsung. Ini bukan versi paling optimal yang saya miliki, tapi itu agak lebih lama karena harus menyimpan struktur pohon dan juga nilainya.

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
sumber