java 如何设计一种算法来计算倒计时式数学数字拼图

How to design an algorithm to calculate countdown style maths number puzzle

提问by drlobo

I have always wanted to do this but every time I start thinking about the problem it blows my mind because of its exponential nature.

我一直想这样做，但每次我开始考虑这个问题时，它都会因为它的指数性质而让我大吃一惊。

The problem solver I want to be able to understand and code is for the countdown maths problem:

我希望能够理解和编码的问题解决者用于倒计时数学问题：

Given set of number X1 to X5 calculate how they can be combined using mathematical operations to make Y. You can apply multiplication, division, addition and subtraction.

给定一组数字 X1 到 X5，计算如何使用数学运算将它们组合成 Y。您可以应用乘法、除法、加法和减法。

So how does 1,3,7,6,8,3make 348?

那么1,3,7,6,8,3make 是怎么做的348呢？

Answer: (((8 * 7) + 3) -1) *6 = 348.

答：(((8 * 7) + 3) -1) *6 = 348。

How to write an algorithm that can solve this problem? Where do you begin when trying to solve a problem like this? What important considerations do you have to think about when designing such an algorithm?

如何写一个算法来解决这个问题？在尝试解决这样的问题时，您从哪里开始？在设计这样的算法时，您必须考虑哪些重要的考虑因素？

采纳答案by Ondrej Bozek

Very quick and dirty solution in Java:

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

更新

It's basically just simple brute force algorithm with exponential complexity. However you can gain some improvemens by leveraging some heuristic function which will help you to order sequence of numbers or(and) operations you will process in each level of getOperatiosn()function recursion.

它基本上只是具有指数复杂性的简单蛮力算法。但是，您可以通过利用一些启发式函数来获得一些改进，这将帮助您对将在每个getOperatiosn()函数递归级别中处理的数字序列或（和）操作进行排序。

Example of such heuristic function is for example difference between mid result and total target result.

这种启发式函数的例子是例如中间结果和总目标结果之间的差异。

This way however only best-case and average-case complexities get improved. Worst case complexity remains untouched.

然而，这种方式只有最佳情况和平均情况的复杂性得到改善。最坏情况的复杂性保持不变。

Worst case complexity can be improved by some kind of branch cutting. I'm not sure if it's possible in this case.

最坏情况的复杂性可以通过某种分支切割来改善。我不确定在这种情况下是否可能。

回答by High Performance Mark

Sure it's exponential but it's tiny so a good (enough) naive implementation would be a good start. I suggest you drop the usual infix notation with bracketing, and use postfix, it's easier to program. You can always prettify the outputs as a separate stage.

当然它是指数级的，但它很小，所以一个好的（足够）朴素的实现将是一个好的开始。我建议你去掉带有括号的常用中缀符号，而使用后缀，它更容易编程。您始终可以将输出美化为一个单独的阶段。

Start by listing and evaluating all the (valid) sequences of numbers and operators. For example (in postfix):

首先列出和评估所有（有效）数字和运算符序列。例如（在后缀中）：

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

My Java is laughable, I don't come here to be laughed at so I'll leave coding this up to you.

我的 Java 是可笑的，我来这里不是为了被嘲笑，所以我将把编码留给你。

To all the smart people reading this: yes, I know that for even a small problem like this there are smarter approaches which are likely to be faster, I'm just pointing OP towards an initial working solution. Someone else can write the answer with the smarter solution(s).

对于所有阅读本文的聪明人：是的，我知道即使是像这样的小问题，也有可能更快的更聪明的方法，我只是将 OP 指向初始工作解决方案。其他人可以用更智能的解决方案写出答案。

So, to answer your questions:

所以，回答你的问题：

• I begin with an algorithm that I think will lead me quickly to a working solution. In this case the obvious (to me) choice is exhaustive enumeration and testing of all possible calculations.
• If the obvious algorithm looks unappealing for performance reasons I'll start thinking more deeply about it, recalling other algorithms that I know about which are likely to deliver better performance. I may start coding one of those first instead.
• If I stick with the exhaustive algorithm and find that the run-time is, in practice, too long, then I might go back to the previous step and code again. But it has to be worth my while, there's a cost/benefit assessment to be made -- as long as my code can outperform Rachel Riley I'd be satisfied.
• Important considerations include my time vscomputer time, mine costs a helluva lot more.

• 我从一个我认为可以快速引导我找到可行解决方案的算法开始。在这种情况下，显而易见的（对我而言）选择是对所有可能的计算进行详尽的枚举和测试。
• 如果明显的算法由于性能原因看起来没有吸引力，我将开始更深入地思考它，回忆我所知道的其他算法，哪些可能提供更好的性能。我可能会先开始编码其中一个。
• 如果我坚持使用穷举算法并发现实际上运行时间太长，那么我可能会回到上一步并再次编码。但它必须值得我花时间，需要进行成本/收益评估——只要我的代码能胜过 Rachel Riley，我就会感到满意。
• 重要的考虑因素包括我的时间与计算机时间，我的成本要高得多。

回答by mitchnull

A working solution in c++11 below.

下面的 c++11 中的工作解决方案。

The basic idea is to use a stack-based evaluation (see RPN) and convert the viable solutions to infix notationfor display purposes only.

基本思想是使用基于堆栈的评估（请参阅RPN）并将可行的解决方案转换为仅用于显示目的的中缀符号。

If we have Ninput digits, we'll use (N-1)operators, as each operator is binary.

如果我们有N输入数字，我们将使用(N-1)运算符，因为每个运算符都是二进制的。

First we create valid permutationsof operands and operators (the selector_array). A valid permutation is one that can be evaluated without stack underflow and which ends with exactly one value (the result) on the stack. Thus 1 1 +is valid, but 1 + 1is not.

首先，我们创建操作数和运算符（数组）的有效排列selector_。有效的排列是可以在没有堆栈下溢的情况下进行评估的排列，并且在堆栈中以恰好一个值（结果）结束。因此1 1 +是有效的，但1 + 1不是。

We test each such operand-operator permutation with every permutation of operands (the values_array) and every combination of operators (the ops_array). Matching results are pretty-printed.

我们用每个操作数排列（values_数组）和每个运算符组合（ops_数组）来测试每个这样的操作数-运算符排列。匹配结果打印得很漂亮。

Arguments are taken from command line as [-s] <target> <digit>[ <digit>...]. The -sswitch prevents exhaustive search, only the first matching result is printed.

参数从命令行作为[-s] <target> <digit>[ <digit>...]. 该-s开关可防止穷举搜索，只打印第一个匹配结果。

(use ./mathpuzzle 348 1 3 7 6 8 3to get the answer for the original question)

（用于./mathpuzzle 348 1 3 7 6 8 3获取原始问题的答案）

This solution doesn't allow concatenating the input digits to form numbers. That could be added as an additional outer loop.

此解决方案不允许连接输入数字以形成数字。这可以作为额外的外循环添加。

The working code can be downloaded from here. (Note: I updated that code with support for concatenating input digits to form a solution)

可以从这里下载工作代码。（注意：我更新了该代码以支持连接输入数字以形成解决方案）

See code comments for additional explanation.

有关其他解释，请参阅代码注释。

#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's 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;
}

回答by Arne

Input is obviously a set of digits and operators: D={1,3,3,6,7,8,3} and Op={+,-,*,/}. The most straight forward algorithm would be a brute forcesolver, which enumeratesall possible combinations of these sets. Where the elements of set Op can be used as often as wanted, but elements from set D are used exactly once. Pseudo code:

输入显然是一组数字和运算符：D={1,3,3,6,7,8,3} 和 Op={+,-,*,/}。最直接的算法是蛮力求解器，它枚举这些集合的所有可能组合。集合 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

Other than that: read jedrus07's and HPM's answers.

除此之外：阅读 jedrus07 和 HPM 的答案。

回答by bjedrzejewski

I think, you need to strictly define the problem first. What you are allowed to do and what you are not. You can start by making it simple and only allowing multiplication, division, substraction and addition.

我认为，您首先需要严格定义问题。你可以做什么，不可以做什么。您可以从简单开始，只允许乘法、除法、减法和加法。

Now you know your problem space- set of inputs, set of available operations and desired input. If you have only 4 operations and x inputs, the number of combinations is less than:

现在您知道了您的问题空间——输入集、可用操作集和所需输入。如果您只有 4 个操作和 x 个输入，则组合数小于：

The number of order in which you can carry out operations (x!) times the possible choices of operations on every step: 4^x. As you can see for 6 numbers it gives reasonable 2949120 operations. This means that this may be your limit for brute force algorithm.

您可以执行操作的顺序数 (x!) 乘以每一步可能的操作选择：4^x。正如您所看到的，对于 6 个数字，它提供了合理的 2949120 次操作。这意味着这可能是您对蛮力算法的限制。

Once you have brute force and you know it works, you can start improving your algorithm with some sort of A* algorithmwhich would require you to define heuristic functions.

一旦你有了蛮力并且你知道它是有效的，你就可以开始使用某种A* 算法来改进你的算法，这需要你定义启发式函数。

In my opinion the best way to think about it is as the search problem. The main difficulty will be finding good heuristics, or ways to reduce your problem space (if you have numbers that do not add up to the answer, you will need at least one multiplication etc.). Start small, build on that and ask follow up questions once you have some code.

在我看来，最好的思考方式是将其视为搜索问题。主要的困难将是找到好的启发式方法，或减少问题空间的方法（如果您的数字加起来不等于答案，则至少需要进行一次乘法等）。从小处着手，在此基础上再接再厉，一旦你有了一些代码，就可以提出后续问题。

回答by Angelo Wentzler

By far the easiest approach is to intelligently brute force it. There is only a finite amount of expressions you can build out of 6 numbers and 4 operators, simply go through all of them.

到目前为止，最简单的方法是智能地暴力破解它。您只能用 6 个数字和 4 个运算符构建有限数量的表达式，只需遍历所有这些表达式即可。

How many? Since you don't have to use all numbers and may use the same operator multiple times, This problem is equivalent to "how many labeled strictly binary trees (aka full binary trees) can you make with at most 6 leaves, and four possible labels for each non-leaf node?".

多少？由于您不必使用所有数字并且可以多次使用相同的运算符，因此该问题等效于“最多可以使用 6 个叶子和四个可能的标签制作多少个带标签的严格二叉树（又名完整二叉树）对于每个非叶节点？”。

The amount of full binary trees with n leaves is equal to catalan(n-1). You can see this as follows:

具有 n 个叶子的完整二​​叉树的数量等于 catalan(n-1)。你可以看到如下：

Every full binary tree with n leaves has n-1 internal nodes and corresponds to a non-full binary tree with n-1 nodes in a unique way (just delete all the leaves from the full one to get it). There happen to be catalan(n) possible binary trees with n nodes, so we can say that a strictly binary tree with n leaves has catalan(n-1) possible different structures.

每个有 n 个叶子的全二叉树都有 n-1 个内部节点，并以一种独特的方式对应一个有 n-1 个节点的非全二叉树（只需删除完整的叶子中的所有叶子即可）。恰好有具有 n 个节点的 catalan(n) 可能的二叉树，因此我们可以说具有 n 个叶子的严格二叉树具有 catalan(n-1) 可能的不同结构。

There are 4 possible operators for each non-leaf node: 4^(n-1) possibilities The leaves can be numbered in n! * (6 choose (n-1)) different ways. (Divide this by k! for each number that occurs k times, or just make sure all numbers are different)

每个非叶子节点有 4 个可能的操作符： 4^(n-1) 种可能性叶子可以用 n 编号！* (6 选择 (n-1)) 种不同的方式。（对每个出现 k 次的数字除以 k！，或者只是确保所有数字都不同）

So for 6 different numbers and 4 possible operators you get Sum(n=1...6) [ Catalan(n-1) * 6!/(6-n)! * 4^(n-1) ] possible expressions for a total of 33,665,406. Not a lot.

因此，对于 6 个不同的数字和 4 个可能的运算符，您将得到 Sum(n=1...6) [ Catalan(n-1) * 6!/(6-n)! * 4^(n-1) ] 总共 33,665,406 个可能的表达式。不是很多。

How do you enumerate these trees?

你如何列举这些树？

Given a collection of all trees with n-1 or less nodes, you can create all trees with n nodes by systematically pairing all of the n-1 trees with the empty tree, all n-2 trees with the 1 node tree, all n-3 trees with all 2 node tree etc. and using them as the left and right sub trees of a newly formed tree.

给定具有 n-1 或更少节点的所有树的集合，您可以通过系统地将所有 n-1 树与空树配对，所有 n-2 树与 1 节点树配对，所有 n 来创建所有具有 n 个节点的树-3 棵树，包含所有 2 个节点树等，并将它们用作新形成的树的左右子树。

So starting with an empty set you first generate the tree that has just a root node, then from a new root you can use that either as a left or right sub tree which yields the two trees that look like this: / and . And so on.

因此，从一个空集开始，您首先生成只有一个根节点的树，然后从一个新根开始，您可以将其用作左子树或右子树，从而产生如下所示的两棵树： / 和 。等等。

You can turn them into a set of expressions on the fly (just loop over the operators and numbers) and evaluate them as you go until one yields the target number.

您可以将它们即时转换为一组表达式（只需循环运算符和数字）并在执行过程中评估它们，直到产生目标数字。

回答by Pulsar

I've written my own countdown solver, in Python.

我用 Python 编写了自己的倒计时求解器。

Here's the code; it is also available on GitHub:

这是代码；它也可以在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()

The algorithm works as follows:

该算法的工作原理如下：

1. The numbers are put into a tuple of length 6 in descending order. Then, all unique subgroups of lengths 1 to 6 are created, the smallest groups first.

   Example: (75, 50, 5, 9, 1, 1) -> {(75), (50), (9), (5), (1), (75, 50), (75, 9), (75, 5), ..., (75, 50, 9, 5, 1, 1)}.

2. Next, the groups are organised into a hierarchical tree: every group is partitioned into all unique unordered pairs of its non-empty subgroups.

   Example: (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. Within each group of numbers, the calculations are performed and the results are stored. For groups of length 1, the result is simply the number itself. For larger groups, the calculations are carried out on every pair of subgroups: in each pair, all results of the first subgroup are combined with all results of the second subgroup using +, -, x and /, and the valid outcomes are stored.

   Example: (75, 5) consists of the pair ((75), (5)). The result of (75) is 75; the result of (5) is 5; the results of (75, 5) are [75+5=80, 75-5=70, 75*5=375, 75/5=15].

4. In this manner, all results are generated, from the smallest groups to the largest. Finally, the algorithm iterates through all results and selects the ones that are the closest match to the target number.

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. 以这种方式，生成所有结果，从最小的组到最大的组。最后，算法遍历所有结果并选择与目标数字最接近的匹配结果。

For a group of m numbers, the maximum number of arithmetic computations is

对于一组 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))

For all groups of length 1 to 6, the maximum total number of computations is then

对于所有长度为 1 到 6 的组，最大总计算次数为

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

which is 1144386. In practice, it will be much less, because the algorithm reuses the results of duplicate groups, ignores trivial operations (adding 0, multiplying by 1, etc), and because the rules of the game dictate that intermediate results must be positive integers (which limits the use of the division operator).

这是 1144386。在实践中，它会少得多，因为算法重用重复组的结果，忽略琐碎的操作（加 0、乘以 1 等），并且因为游戏规则规定中间结果必须是正整数（限制除法运算符的使用）。

回答by Alan Swindells

I wrote a slightly simpler version:

我写了一个稍微简单的版本：

1. for every combination of 2 (distinct) elements from the list and combine them using +,-,*,/ (note that since a>b then only a-b is needed and only a/b if a%b=0)
2. if combination is target then record solution
3. recursively call on the reduced lists

1. 对于列表中 2 个（不同的）元素的每个组合，并使用 +,-,*,/ 组合它们（注意，由于 a>b，则只需要 ab，如果 a%b=0，则只需要 a/b）
2. 如果组合是目标，则记录解决方案
3. 递归调用减少的列表