将集合中的项目求和以获得目标值的方式数量-订单很重要 [英] Number of ways to sum the items in a set to get a target value - Order matters

问题描述

我正在为编程面试做练习，我在GlassDoor上偶然发现了一个问题:找到我们可以对集合中的项求和以达到目标值的方法数量.定单很重要."

I'm practicing for programming interviews, and I stumbled upon this question on GlassDoor: "Find the number of ways we can sum the items in the set to get our target value. Order matters."

显然，面试官无法提供答案，但他在GlassDoor上留下了这一评论:这更多是数学问题，而不是编程问题."

Apparently, the interviewer couldn't come up with an answer, but he left this comment on GlassDoor: "This was more of a math question than a programming question."

此问题似乎与以下问题不同:

This problem seems to be different than this one: Finding all possible combinations of numbers to reach a given sum.

所以我的问题是:鉴于顺序很重要，解决该问题的正确方法是什么?而且，什么是一种有效的算法来解决找到所有方法以求和集合中的各项以达到目标值并且顺序很重要的问题呢?

So my questions is: what is the correct approach to solve this problem, given that order matters? And also, what would be an efficient algorithm to solve the problem of finding all the ways to sum the items in the set to reach the target value, and order matters?

如果您可以提供有效的代码，那就太好了.另外，我正在用Java进行练习，所以我更喜欢Java解决方案，但是任何一种语言也可以.

If you can provide working code, that would be awesome. Also, I'm practicing in Java, so I'd prefer a Java solution, but any language would also be fine.

非常感谢.

推荐答案

这就像一个做出更改的问题，但是您不想要最少数量的硬币"，而是想知道方法的数量.此外，重要的是要注意顺序很重要.使用动态编程，如下所示.假设我们要展示如何从顺序无关紧要的1、3、5的总和中得出10(即1 + 3 + 1 + 5与1 + 1 + 3 + 5相同).制作索引为10的数组(11个项目).您可以用1种方式设定00.所有负索引都可以通过0种方式进行.

This is like a change-making problem, but you don't want the minimum number of "coins", you want to keep track of the number of ways. Furthermore, it is important to note that order matters. Use dynamic programming as follows. Suppose we want to show how to make 10 from sums of 1, 3, 5 where order doesn't matter (i.e. 1 + 3 + 1 + 5 is the same as 1 + 1 + 3 + 5). Make an array indexed to 10 (11 items). You can make 00 in 1 way. All negative indexes can be made in 0 ways.

00 01 02 03 04 05 06 07 08 09 10
 1

然后计算出1的制造方法的数量.如果从1中减去硬币值1，则得到1.如果从1中减去任何较大的硬币值，则得到的负指数表示零方法.您将结果相加1方式(减去1)+ 0方式(减去3)+ 0方式(减去5).所以我们有

You then count the number of ways you can make 1. If you subtract coin value 1 from 1 you get 1. If you subtract any larger coin value from 1, you get a negative index which means zero ways. You sum up the results 1 way (subtracting 1) + 0 ways (subtracting 3) + 0 ways (subtracting 5). So we have

00 01 02 03 04 05 06 07 08 09 10
 1  1

取值为2.我们可以减去1美分硬币以获得1，其中1种方式； 3美分硬币可获得-1，其中有0种方式； 5分硬币得到-3，其中有0种方法.总共1 + 0 + 0 = 1种方式可获得2美分.

Take a value of 2. We can subtract 1 cent coin to get 1 of which there is 1 way; 3 cent coin to get -1 of which there is 0 ways; 5 cent coin to get -3 of which there is 0 ways. Total 1 + 0 + 0 = 1 way to get 2 cents.

00 01 02 03 04 05 06 07 08 09 10
 1  1  1

对于3美分，我们可以减去1以获取2美分的所有更改方式，或者减去3美分以获取0美分的所有更改方式，或者减去5美分以访问-2的所有更改方式.美分方式的总和是1 +1 + 0 = 2.

For 3 cents, we can subtract 1 to access all the ways of making change for 2 cents, or subtract 3 cents to access all the ways of making 0 cents, or subtract 5 cents to access all the ways of making -2 cents; sum of ways is 1 + 1 + 0 = 2.

00 01 02 03 04 05 06 07 08 09 10
 1  1  1  2

花4美分，我们可以用2 +1 + 0 = 3种方式来做.但是，请注意，这3种方式包括1 + 1 + 1 + 1、3 + 1和1 + 3. 1 + 3和3 + 1属于不同的类别，因为它们以不同的数字结尾.

For 4 cents, we can do it in 2 + 1 + 0 = 3 ways. However, note that the 3 ways include 1+1+1+1, 3+1, and 1+3. 1+3 and 3+1 are in different categories since they end in different numbers.

以这种方式继续

 00 01 02 03 04 05 06 07 08 09 10
  1  1  1  2  3  5  8 12 19 30 47

现在我们知道如何构造数字了，我们可以寻找更快的方法.请注意，我们必须处理前几个的负索引，这有点混乱，因此我们不妨从给定的前5个值开始.现在我们需要计算的是一个递归函数:f(n) = f(n-1) + f(n-3) + f(n-5)，条件是上表给出f(0),...,f(4).

Now that we see how to construct the numbers, we can look for faster ways of doing so. Note that we have to deal with negative indices for the first few, which is a bit messy, so we might as well start with the first 5 values as given. What we need to calculate now is a recursive function: f(n) = f(n-1) + f(n-3) + f(n-5) with the condition that f(0),...,f(4) are given by the table above.

有很多方法可以计算递归函数.在这里，它成为对知识深度的真实测试.天真的方法是在编程语言中使用递归.第一个问题是您的数字将溢出，因为f呈指数增长.您可以使用long而不是int暂时缓解这种情况.但是long也会很快溢出，因此您必须使用BigInteger才能获得n大于(大约20)左右的n的精确结果.

There are many ways to calculate that recursive function. This is where it becomes a real test of depth of knowledge. The naive approach would be to use recursion in the programming language. The first problem would be that your numbers will overflow because f has exponential growth. You can mitigate that situation for a time by using long instead of int. But long will quickly overflow too, so you'll have to use BigInteger to get exact results for n bigger than (I'm guessing) 20 or so.

接下来，使用递归函数将很慢，因为计算f(n)可能涉及一遍又一遍地重新计算较小的f(x).为了缓解该问题，请使用备忘录为较小的值存储f(x).接下来，如果尝试从较大的n到较小的值进行计算，则会遇到堆栈溢出的情况.如果要为特定的n计算，则应该从较低的值开始计算，而不是从较高的n值开始计算.

Next, using recursive functions will be slow, because calculating f(n) might involve recalculating smaller f(x) over and over again. To mitigate that problem, use memoization to store f(x) for smaller values. Next, you'll experience stack overflow if you try to calculate from larger n to smaller. If you're calculating for a particular n, you should build up from lower values, instead of down from higher values of n.

接下来，您将遇到内存不足的情况.您可以通过不记住x随x的增加而忽略每个f(x)值，而仅记住最后一个5值(在我的示例中)来解决此问题.最终，您将体验到内存不足而无法存储BigIntegers的问题，但是除非问题改变，否则您将无能为力.

Next, you'll experience out of memory. You can get around that by not remembering every value of f(x) as x increases, but only the last 5 values (in my example). Eventually you'll experience out of memory storing BigIntegers, but there's nothing you can do about that unless the question changes.

如果要提高程序速度，可以使用更多的加速功能.可以用log n操作而不是n操作来计算f(n)，其方式如下.请注意，有一种写递归的矩阵乘法方式，其中在每个阶段我们都需要记住5个值来计算下一个:

There are some more accelerations you can use if you're looking to improve the speed of the program. f(n) can be computed in log n operations rather than n operations in the following manner. Note that there is a matrix multiplication way of writing the recursion, where at each stage we need to remember 5 values to calculate the next one:

 |1 0 1 0 1| |f(n-1)|   | f(n) |
 |1 0 0 0 0| |f(n-2)|   |f(n-1)|
 |0 1 0 0 0| |f(n-3)| = |f(n-2)|
 |0 0 1 0 0| |f(n-4)|   |f(n-3)|
 |0 0 0 1 0| |f(n-5)|   |f(n-4)|

因此，如果我们可以计算矩阵的幂，则可以计算f(n):

So we can calculate f(n) if we can calculate powers of the matrix:

 |1 0 1 0 1|^(n-4)
 |1 0 0 0 0|
 |0 1 0 0 0|
 |0 0 1 0 0|
 |0 0 0 1 0|

我们可以使用n的二进制扩展来加速该过程.假设n = 6，就像我们想要f(10)那样.请注意，6 = 4 + 2为二进制.用M表示矩阵.我们有M^1.我们先计算M^2 = M^1 * M^1和M^4 = M^2 * M^2，然后计算M^6 = M^2 * M^4.

We can accelerate that process by using the binary expansion of n. Suppose n = 6, as it would be if we wanted f(10). Note that 6 = 4 + 2 in binary. Denote the matrix by M. We have M^1. We calculate M^2 = M^1 * M^1 and M^4 = M^2 * M^2, then M^6 = M^2 * M^4.

根据具体示例，可能还会有其他加速，但这应该可以帮助您入门.

There may be other accelerations, depending on the particular example, but that should get you started.

这篇关于将集合中的项目求和以获得目标值的方式数量-订单很重要的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！