Как разработать алгоритм для расчета голограммы

Ответ 1

Очень быстрое и грязное решение в Java:

public class JavaApplication1
{

    public static void main(String[] args)
    {
        List<Integer> list = Arrays.asList(1, 3, 7, 6, 8, 3);
        for (Integer integer : list) {
            List<Integer> runList = new ArrayList<>(list);
            runList.remove(integer);
            Result result = getOperations(runList, integer, 348);
            if (result.success) {
                System.out.println(integer + result.output);
                return;
            }
        }
    }

    public static class Result
    {

        public String output;
        public boolean success;
    }

    public static Result getOperations(List<Integer> numbers, int midNumber, int target)
    {
        Result midResult = new Result();
        if (midNumber == target) {
            midResult.success = true;
            midResult.output = "";
            return midResult;
        }
        for (Integer number : numbers) {
            List<Integer> newList = new ArrayList<Integer>(numbers);
            newList.remove(number);
            if (newList.isEmpty()) {
                if (midNumber - number == target) {
                    midResult.success = true;
                    midResult.output = "-" + number;
                    return midResult;
                }
                if (midNumber + number == target) {
                    midResult.success = true;
                    midResult.output = "+" + number;
                    return midResult;
                }
                if (midNumber * number == target) {
                    midResult.success = true;
                    midResult.output = "*" + number;
                    return midResult;
                }
                if (midNumber / number == target) {
                    midResult.success = true;
                    midResult.output = "/" + number;
                    return midResult;
                }
                midResult.success = false;
                midResult.output = "f" + number;
                return midResult;
            } else {
                midResult = getOperations(newList, midNumber - number, target);
                if (midResult.success) {
                    midResult.output = "-" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber + number, target);
                if (midResult.success) {
                    midResult.output = "+" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber * number, target);
                if (midResult.success) {
                    midResult.output = "*" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber / number, target);
                if (midResult.success) {
                    midResult.output = "/" + number + midResult.output;
                    return midResult
                }
            }

        }
        return midResult;
    }
}

UPDATE

Это просто простой алгоритм грубой силы с экспоненциальной сложностью. Однако вы можете получить некоторые импровизации, используя некоторую эвристическую функцию, которая поможет вам упорядочить последовательность чисел или (и) операций, которые вы будете обрабатывать на каждом уровне рекурсии функции getOperatiosn().

Пример такой эвристической функции - это, например, разность между средним результатом и итоговым целевым результатом.

Таким образом, улучшаются только наилучшие и средние сложности. Худшая сложность случая остается нетронутой.

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

Ответ 2

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

Начните с перечисления и оценки всех (действительных) последовательностей чисел и операторов. Например (в постфикс):

1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26

Моя Java смехотворна, я не прихожу сюда, чтобы ее рассмешили, поэтому я оставлю вам эту кодировку.

Для всех умных людей, читающих это: да, я знаю, что даже для небольшой проблемы вроде этого есть более разумные подходы, которые, вероятно, будут быстрее, я просто указываю OP на начальное рабочее решение. Кто-то может написать ответ с помощью более разумного решения.

Итак, чтобы ответить на ваши вопросы:

• Начну с алгоритма, который, как я думаю, быстро приведет меня к рабочему решению. В этом случае очевидным (для меня) выбором является исчерпывающее перечисление и тестирование всех возможных вычислений.
• Если очевидный алгоритм выглядит непривлекательным по соображениям производительности, я начну думать об этом глубже, вспомнив другие алгоритмы, о которых я знаю, которые могут обеспечить лучшую производительность. Вместо этого я могу начать кодирование одного из них.
• Если я придерживаюсь исчерпывающего алгоритма и обнаруживаю, что время выполнения на практике слишком длительное, я могу вернуться к предыдущему шагу и коду снова. Но это должно стоить того времени, там будет оценка затрат/выгод - пока мой код может опередить Рэйчел Райли, я был бы доволен.
• Важные соображения включают мое время в сравнении с компьютерным временем, моя стоимость стоит больше.

Ответ 3

Рабочее решение в С++ 11 ниже.

Основная идея заключается в использовании оценки на основе стека (см. RPN) и преобразовании жизнеспособных решений в инфиксную нотацию только для отображения.

Если у нас есть входные цифры N, мы будем использовать операторы (N-1), поскольку каждый оператор является двоичным.

Сначала мы создаем допустимые перестановки операндов и операторов (массив selector_). Допустимая перестановка - это такая, которая может быть оценена без потери значения в стеке и заканчивается ровно одним значением (результатом) в стеке. Таким образом, 1 1 + является действительным, а 1 + 1 - нет.

Мы проверяем каждую такую перестановку операндов-операторов с каждой перестановкой операндов (массив values_) и каждой комбинацией операторов (массив ops_). Соответствующие результаты хорошо напечатаны.

Аргументы взяты из командной строки как [-s] <target> <digit>[ <digit>...]. Переключатель -s предотвращает исчерпывающий поиск, печатается только первый соответствующий результат.

(используйте ./mathpuzzle 348 1 3 7 6 8 3, чтобы получить ответ на оригинальный вопрос)

Это решение не позволяет объединять входные цифры в числа. Это может быть добавлено в качестве дополнительного внешнего цикла.

Рабочий код можно скачать с здесь. (Примечание: я обновил этот код с поддержкой объединения входных цифр для формирования решения)

См. комментарии к коду для дополнительного объяснения.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iterator>
#include <string>

namespace {

enum class Op {
    Add,
    Sub,
    Mul,
    Div,
};

const std::size_t NumOps = static_cast<std::size_t>(Op::Div) + 1;
const Op FirstOp = Op::Add;

using Number = int;

class Evaluator {
    std::vector<Number> values_; // stores our digits/number we can use
    std::vector<Op> ops_; // stores the operators
    std::vector<char> selector_; // used to select digit (0) or operator (1) when evaluating. should be std::vector<bool>, but that broken

    template <typename T>
    using Stack = std::stack<T, std::vector<T>>;

    // checks if a given number/operator order can be evaluated or not
    bool isSelectorValid() const {
        int numValues = 0;
        for (auto s : selector_) {
            if (s) {
                if (--numValues <= 0) {
                    return false;
                }
            }
            else {
                ++numValues;
            }
        }
        return (numValues == 1);
    }

    // evaluates the current values_ and ops_ based on selector_
    Number eval(Stack<Number> &stack) const {
        auto vi = values_.cbegin();
        auto oi = ops_.cbegin();
        for (auto s : selector_) {
            if (!s) {
                stack.push(*(vi++));
                continue;
            }
            Number top = stack.top();
            stack.pop();
            switch (*(oi++)) {
                case Op::Add:
                    stack.top() += top;
                    break;
                case Op::Sub:
                    stack.top() -= top;
                    break;
                case Op::Mul:
                    stack.top() *= top;
                    break;
                case Op::Div:
                    if (top == 0) {
                        return std::numeric_limits<Number>::max();
                    }
                    Number res = stack.top() / top;
                    if (res * top != stack.top()) {
                        return std::numeric_limits<Number>::max();
                    }
                    stack.top() = res;
                    break;
            }
        }
        Number res = stack.top();
        stack.pop();
        return res;
    }

    bool nextValuesPermutation() {
        return std::next_permutation(values_.begin(), values_.end());
    }

    bool nextOps() {
        for (auto i = ops_.rbegin(), end = ops_.rend(); i != end; ++i) {
            std::size_t next = static_cast<std::size_t>(*i) + 1;
            if (next < NumOps) {
                *i = static_cast<Op>(next);
                return true;
            }
            *i = FirstOp;
        }
        return false;
    }

    bool nextSelectorPermutation() {
        // the start permutation is always valid
        do {
            if (!std::next_permutation(selector_.begin(), selector_.end())) {
                return false;
            }
        } while (!isSelectorValid());
        return true;
    }

    static std::string buildExpr(const std::string& left, char op, const std::string &right) {
        return std::string("(") + left + ' ' + op + ' ' + right + ')';
    }

    std::string toString() const {
        Stack<std::string> stack;
        auto vi = values_.cbegin();
        auto oi = ops_.cbegin();
        for (auto s : selector_) {
            if (!s) {
                stack.push(std::to_string(*(vi++)));
                continue;
            }
            std::string top = stack.top();
            stack.pop();
            switch (*(oi++)) {
                case Op::Add:
                    stack.top() = buildExpr(stack.top(), '+', top);
                    break;
                case Op::Sub:
                    stack.top() = buildExpr(stack.top(), '-', top);
                    break;
                case Op::Mul:
                    stack.top() = buildExpr(stack.top(), '*', top);
                    break;
                case Op::Div:
                    stack.top() = buildExpr(stack.top(), '/', top);
                    break;
            }
        }
        return stack.top();
    }

public:
    Evaluator(const std::vector<Number>& values) :
            values_(values),
            ops_(values.size() - 1, FirstOp),
            selector_(2 * values.size() - 1, 0) {
        std::fill(selector_.begin() + values_.size(), selector_.end(), 1);
        std::sort(values_.begin(), values_.end());
    }

    // check for solutions
    // 1) we create valid permutations of our selector_ array (eg: "1 1 + 1 +",
    //    "1 1 1 + +", but skip "1 + 1 1 +" as that cannot be evaluated
    // 2) for each evaluation order, we permutate our values
    // 3) for each value permutation we check with each combination of
    //    operators
    // 
    // In the first version I used a local stack in eval() (see toString()) but
    // it turned out to be a performance bottleneck, so now I use a cached
    // stack. Reusing the stack gives an order of magnitude speed-up (from
    // 4.3sec to 0.7sec) due to avoiding repeated allocations.  Using
    // std::vector as a backing store also gives a slight performance boost
    // over the default std::deque.
    std::size_t check(Number target, bool singleResult = false) {
        Stack<Number> stack;

        std::size_t res = 0;
        do {
            do {
                do {
                    Number value = eval(stack);
                    if (value == target) {
                        ++res;
                        std::cout << target << " = " << toString() << "\n";
                        if (singleResult) {
                            return res;
                        }
                    }
                } while (nextOps());
            } while (nextValuesPermutation());
        } while (nextSelectorPermutation());
        return res;
    }
};

} // namespace

int main(int argc, const char **argv) {
    int i = 1;
    bool singleResult = false;
    if (argc > 1 && std::string("-s") == argv[1]) {
        singleResult = true;
        ++i;
    }
    if (argc < i + 2) {
        std::cerr << argv[0] << " [-s] <target> <digit>[ <digit>]...\n";
        std::exit(1);
    }
    Number target = std::stoi(argv[i]);
    std::vector<Number> values;
    while (++i <  argc) {
        values.push_back(std::stoi(argv[i]));
    }
    Evaluator evaluator{values};
    std::size_t res = evaluator.check(target, singleResult);
    if (!singleResult) {
        std::cout << "Number of solutions: " << res << "\n";
    }
    return 0;
}

Ответ 4

Ввод, очевидно, представляет собой набор цифр и операторов: D = {1,3,3,6,7,8,3} и Op = {+, -, *,/}. Наиболее прямым алгоритмом будет грубая сила решатель, который перечисляет все возможные комбинации этих множеств. Если элементы set Op могут использоваться так часто, как требуется, но элементы из набора D используются ровно один раз. Псевдокод:

D={1,3,3,6,7,8,3}
Op={+,-,*,/}
Solution=348
for each permutation D_ of D:
   for each binary tree T with D_ as its leafs:
       for each sequence of operators Op_ from Op with length |D_|-1:
           label each inner tree node with operators from Op_
           result = compute T using infix traversal
           if result==Solution
              return T
return nil

Кроме этого: прочитайте ответы jedrus07 и HPM.

Ответ 5

Я думаю, вам нужно строго определить проблему в первую очередь. Что вам разрешено делать, а что нет. Вы можете начать с упрощения и только для умножения, деления, вычитания и добавления.

Теперь вы знаете свой проблемный объемный набор входов, набор доступных операций и желаемый ввод. Если у вас всего 4 операции и x входов, количество комбинаций меньше:

Число порядков, в которых вы можете выполнять операции (x!) раз по возможности выбора операций на каждом шаге: 4 ^ x. Как вы можете видеть на 6 номеров, он дает разумные 2949120 операций. Это означает, что это может быть вашим пределом для алгоритма грубой силы.

Когда у вас есть грубая сила, и вы знаете, что она работает, вы можете начать улучшать свой алгоритм с помощью своего рода алгоритма A *, который потребует от вас для определения эвристических функций.

На мой взгляд, лучший способ подумать об этом - это проблема поиска. Основная трудность будет заключаться в поиске хорошей эвристики или способах сокращения вашего проблемного пространства (если у вас есть номера, которые не совпадают с ответом, вам потребуется как минимум одно умножение и т.д.). Начните с малого, опираясь на это и задайте следующие вопросы, когда у вас есть код.

Ответ 6

Я давно нашел отличный алгоритм из Oxford Computer Science Docs (с исходным кодом Java). И я восхищаюсь им каждый раз, когда читаю это решение. Я считаю, что это будет полезно.

Ответ 7

Безусловно, самый простой подход заключается в том, чтобы разумно перебрать его. Из 6 чисел и 4 операторов можно составить лишь конечное количество выражений, просто просмотрите их все.

Сколько? Поскольку вам не нужно использовать все числа и вы можете использовать один и тот же оператор несколько раз, эта проблема эквивалентна тому, сколько "помеченных строго двоичных деревьев (или полных двоичных деревьев) вы можете сделать с максимум 6 листами и четырьмя возможными метками" для каждого неконечного узла? ".

Количество полных бинарных деревьев с n листьями равно каталонскому (n-1). Вы можете увидеть это следующим образом:

Каждое полное двоичное дерево с n листьями имеет n-1 внутренних узлов и уникальным образом соответствует неполному двоичному дереву с n-1 узлами (просто удалите все листья из полного, чтобы получить его). Возможно, существуют каталонские (n) возможные бинарные деревья с n узлами, поэтому мы можем сказать, что строго бинарное дерево с n листьями имеет каталонские (n-1) возможные различные структуры.

Для каждого неконечного узла есть 4 возможных оператора: 4 ^ (n-1) возможностей Листья могут быть пронумерованы на n! * (6 выберите (n-1)) разными способами. (Разделите это на k! Для каждого числа, встречающегося k раз, или просто убедитесь, что все числа разные)

Таким образом, для 6 различных чисел и 4 возможных операторов вы получаете сумму (n = 1... 6) [каталанский (n-1) * 6!/(6-n)! * 4 ^ (n-1)] возможных выражений на общую сумму 33 665 406. Не много.

Как вы перечисляете эти деревья?

Учитывая набор всех деревьев с n-1 или менее узлами, вы можете создать все деревья с n узлами, систематически объединяя все n-1 деревья с пустым деревом, все n-2 дерева с деревом 1 узла, все n -3 дерева со всеми двумя деревьями узлов и т.д. И использование их в качестве левого и правого поддеревьев вновь образованного дерева.

Итак, начиная с пустого набора, вы сначала генерируете дерево, которое имеет только корневой узел, затем из нового корня вы можете использовать его как левое или правое поддерево, которое выдает два дерева, которые выглядят так:/и. И так далее.

Вы можете превратить их в набор выражений на лету (просто циклически по операторам и числам) и оценивать их, пока вы не получите целевое число.

Ответ 8

Я написал свой собственный решатель обратного отсчета в Python.

Здесь код; он также доступен на GitHub:

#!/usr/bin/env python3

import sys
from itertools import combinations, product, zip_longest
from functools import lru_cache

assert sys.version_info >= (3, 6)


class Solutions:

    def __init__(self, numbers):
        self.all_numbers = numbers
        self.size = len(numbers)
        self.all_groups = self.unique_groups()

    def unique_groups(self):
        all_groups = {}
        all_numbers, size = self.all_numbers, self.size
        for m in range(1, size+1):
            for numbers in combinations(all_numbers, m):
                if numbers in all_groups:
                    continue
                all_groups[numbers] = Group(numbers, all_groups)
        return all_groups

    def walk(self):
        for group in self.all_groups.values():
            yield from group.calculations


class Group:

    def __init__(self, numbers, all_groups):
        self.numbers = numbers
        self.size = len(numbers)
        self.partitions = list(self.partition_into_unique_pairs(all_groups))
        self.calculations = list(self.perform_calculations())

    def __repr__(self):
        return str(self.numbers)

    def partition_into_unique_pairs(self, all_groups):
        # The pairs are unordered: a pair (a, b) is equivalent to (b, a).
        # Therefore, for pairs of equal length only half of all combinations
        # need to be generated to obtain all pairs; this is set by the limit.
        if self.size == 1:
            return
        numbers, size = self.numbers, self.size
        limits = (self.halfbinom(size, size//2), )
        unique_numbers = set()
        for m, limit in zip_longest(range((size+1)//2, size), limits):
            for numbers1, numbers2 in self.paired_combinations(numbers, m, limit):
                if numbers1 in unique_numbers:
                    continue
                unique_numbers.add(numbers1)
                group1, group2 = all_groups[numbers1], all_groups[numbers2]
                yield (group1, group2)

    def perform_calculations(self):
        if self.size == 1:
            yield Calculation.singleton(self.numbers[0])
            return
        for group1, group2 in self.partitions:
            for calc1, calc2 in product(group1.calculations, group2.calculations):
                yield from Calculation.generate(calc1, calc2)

    @classmethod
    def paired_combinations(cls, numbers, m, limit):
        for cnt, numbers1 in enumerate(combinations(numbers, m), 1):
            numbers2 = tuple(cls.filtering(numbers, numbers1))
            yield (numbers1, numbers2)
            if cnt == limit:
                return

    @staticmethod
    def filtering(iterable, elements):
        # filter elements out of an iterable, return the remaining elements
        elems = iter(elements)
        k = next(elems, None)
        for n in iterable:
            if n == k:
                k = next(elems, None)
            else:
                yield n

    @staticmethod
    @lru_cache()
    def halfbinom(n, k):
        if n % 2 == 1:
            return None
        prod = 1
        for m, l in zip(reversed(range(n+1-k, n+1)), range(1, k+1)):
            prod = (prod*m)//l
        return prod//2


class Calculation:

    def __init__(self, expression, result, is_singleton=False):
        self.expr = expression
        self.result = result
        self.is_singleton = is_singleton

    def __repr__(self):
        return self.expr

    @classmethod
    def singleton(cls, n):
        return cls(f"{n}", n, is_singleton=True)

    @classmethod
    def generate(cls, calca, calcb):
        if calca.result < calcb.result:
            calca, calcb = calcb, calca
        for result, op in cls.operations(calca.result, calcb.result):
            expr1 = f"{calca.expr}" if calca.is_singleton else f"({calca.expr})"
            expr2 = f"{calcb.expr}" if calcb.is_singleton else f"({calcb.expr})"
            yield cls(f"{expr1} {op} {expr2}", result)

    @staticmethod
    def operations(x, y):
        yield (x + y, '+')
        if x > y:                     # exclude non-positive results
            yield (x - y, '-')
        if y > 1 and x > 1:           # exclude trivial results
            yield (x * y, 'x')
        if y > 1 and x % y == 0:      # exclude trivial and non-integer results
            yield (x // y, '/')


def countdown_solver():
    # input: target and numbers. If you want to play with more or less than
    # 6 numbers, use the second version of 'unsorted_numbers'.
    try:
        target = int(sys.argv[1])
        unsorted_numbers = (int(sys.argv[n+2]) for n in range(6))  # for 6 numbers
#        unsorted_numbers = (int(n) for n in sys.argv[2:])         # for any numbers
        numbers = tuple(sorted(unsorted_numbers, reverse=True))
    except (IndexError, ValueError):
        print("You must provide a target and numbers!")
        return

    solutions = Solutions(numbers)
    smallest_difference = target
    bestresults = []
    for calculation in solutions.walk():
        diff = abs(calculation.result - target)
        if diff <= smallest_difference:
            if diff < smallest_difference:
                bestresults = [calculation]
                smallest_difference = diff
            else:
                bestresults.append(calculation)
    output(target, smallest_difference, bestresults)


def output(target, diff, results):
    print(f"\nThe closest results differ from {target} by {diff}. They are:\n")
    for calculation in results:
        print(f"{calculation.result} = {calculation.expr}")


if __name__ == "__main__":
countdown_solver()

Алгоритм работает следующим образом:

1. Числа помещаются в кортеж длиной 6 в порядке убывания. Затем создаются все уникальные подгруппы длиной от 1 до 6, сначала самые маленькие группы.

   Пример: (75, 50, 5, 9, 1, 1) → {(75), (50), (9), (5), (1), (75, 50), (75, 9), (75, 5),..., (75, 50, 9, 5, 1, 1)}.

2. Затем группы организуются в иерархическое дерево: каждая группа разбивается на все уникальные неупорядоченные пары своих непустых подгрупп.

   Пример: (9, 5, 1, 1) → [(9, 5, 1) + (1), (9, 1, 1) + (5), (5, 1, 1) + (9), (9, 5) + (1, 1), (9, 1) + (5, 1)].

3. Внутри каждой группы чисел выполняются вычисления и результаты сохраняются. Для групп длины 1 результатом является просто само число. Для больших групп расчеты выполняются для каждой пары подгрупп: в каждой паре все результаты первой подгруппы объединяются со всеми результатами второй подгруппы с использованием +, -, x и /, и сохраняются действительные результаты.

   Пример: (75, 5) состоит из пары ((75), (5)). Результат (75) равен 75; результат (5) равен 5; результаты (75, 5): [75 + 5 = 80, 75-5 = 70, 75 * 5 = 375, 75/5 = 15].

4. Таким образом, генерируются все результаты, от самых маленьких групп до самых больших. Наконец, алгоритм перебирает все результаты и выбирает те из них, которые наиболее близко соответствуют целевому числу.

Для группы из m чисел максимальное количество арифметических вычислений составляет

comps[m] = 4*sum(binom(m, k)*comps[k]*comps[m-k]//(1 + (2*k)//m) for k in range(1, m//2+1))

Для всех групп длиной от 1 до 6 максимальное общее количество вычислений составляет

total = sum(binom(n, m)*comps[m] for m in range(1, n+1))

это 1144386. На практике это будет намного меньше, потому что алгоритм повторно использует результаты повторяющихся групп, игнорирует тривиальные операции (добавление 0, умножение на 1 и т.д.), а также потому, что правила игры определяют, что промежуточный результаты должны быть положительными целыми числами (что ограничивает использование оператора деления).