java组合与继承始示例

Permutations and Combinations are super useful in so many applications – from Computer Programming to Probability Theory to Genetics.

排列和组合在许多应用中非常有用-从计算机编程到概率论再到遗传学。

I'm going to introduce you to these two concepts side-by-side, so you can see how useful they are.

我将向您并排介绍这两个概念，以便您了解它们的实用性。

The key difference between these two concepts is ordering. With Permutations, you focus on lists of elements where their order matters.

这两个概念之间的主要区别在于排序。 使用Permutations ，您可以关注顺序重要的元素列表 。

For example, I was born in 1977. That's number 1 followed by number 9, followed by number 7, followed by number 7. In that particular order.

例如，我出生于1977年 。 那是数字1，其后是数字9 ，然后是数字7 ，然后是数字7 。 以该特定顺序。

If I change the order to 7917 instead, that would be a completely different year. Thus, the order matters.

如果我将订单更改为7917 ，那将是完全不同的一年。 因此，顺序很重要 。

With Combinations on the other hand, the focus is on groups of elements where the order does not matter.

与在另一方面的组合 ，重点是元素，其中顺序无关紧要的基团 。

Like my cup of coffee is a combination of coffee, sugar and water. It doesn't matter which order I add these ingredients are in. There may as well be water, sugar and coffee, it's still the same cup of coffee. Thus, the order does not matter.

就像我的咖啡是咖啡 ， 糖和水的混合物 。 我添加这些配料的顺序无关紧要。可能还有水 ， 糖和咖啡 ，仍然是同一杯咖啡。 因此，顺序并不重要。

Now let's take a closer look at these concepts.

现在，让我们仔细看看这些概念。

第1部分：排列 (Part 1: Permutations)

允许重复的排列 (Permutations Where Repetition is Allowed)

Imagine you got a new phone. As you start using this new phone, at some point you will be asked to set up a password.

假设您有一部新手机。 当您开始使用此新手机时，有时会要求您设置密码。

The password must consist of 4 digits. Any 4 digits. And they may be repeated.

密码必须由4位数字组成。 任意4位数字。 并且它们可能会重复。

There are 10 digits in total to begin with. Those are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. So for the first digit of your password, you have 10 choices.

开头总共有10位数字。 它们是：0、1、2、3、4、5、6、7、8、9。因此，对于密码的第一位，您有10个选择。

Since you may use the same digit again, the number of choices for the second digit of our password will be 10 again! Thus, choosing two of the password digits so far, the permutations are 10 times 10, or 10 x 10 = 100 or 10².

由于您可能再次使用相同的数字，因此我们密码第二个数字的选择数将再次为10 ！ 因此，到目前为止选择两个密码数字，排列是10乘以10，即10 x 10 = 100或10 ² 。

The same thinking goes for the third digit of your password. You get to choose from the same 10 choices again. This time you will have 10 times 10 times 10, or 10 x 10 x 10 = 1,000 or 10³ permutations.

密码的第三位数字也是一样。 您将再次从相同的10个选择中进行选择。 这次，您将得到10乘以10乘以10 ，或者10 x 10 x 10 = 1,000或10 ³个排列。

At last, for the fourth digit of the password and the same 10 digits to choose from, we end up with 10 times 10 times 10 times 10, or 10 x 10 x 10 x 10 = 10,000 or 10⁴ permutations.

最后，对于密码的第四位数字和可供选择的相同10位数字，我们得到10乘以10乘以10乘以10或10 x 10 x 10 x 10 = 10,000或10 ⁴个排列。

As you probably noticed, you had 4 choices to make and you multiplied 10 four times (10 x 10 x 10 x 10) to arrive at a total number of permutations (10,000). If you had to choose 3 digits for your password, you would multiply 10 three times. If 7, you would do it seven times, and so on.

您可能已经注意到，您有4个选择，然后乘以10 四次 (10 x 10 x 10 x 10)，得出排列总数(10,000)。 如果你不得不选择3个位数密码，你会乘10个三次 。 如果为7 ，则将执行七次 ，依此类推。

But life isn't all about passwords with digits to choose from. What if you have a birthday party and need to choose 5 colored balloons from 20 different colors available?

但是生活并不全都是带有数字可供选择的密码。 如果您要举行生日派对，并且需要从20种不同的颜色中选择5个彩色的气球，该怎么办？

Since you have 20 different colors to choose from and may choose the same color again, for each balloon you have 20 choices. The first balloon is 20, the second balloon is 20 times 20, or 20 x 20 = 400 etc. For the fifth balloon you get 20 x 20 x 20 x 20 x 20 = 3,200,000 or 20⁵ permutations.

由于您有20种不同的颜色可供选择，并且可能会再次选择相同的颜色，因此对于每个气球，您都有20种选择。 第一个气球是20 ，第二个气球是20乘以20 ，或20 x 20 = 400， 依此类推 。对于第五个气球，您得到20 x 20 x 20 x 20 x 20 = 3,200,000或20 ⁵个排列。

Let's summarize with the general rule: when order matters and repetition is allowed, if n is the number of things to choose from (balloons, digits etc), and you choose r of them (5 balloons for the party, 4 digits for the password, etc.), the number of permutations will equal P = n^r.

让我们总结一下一般规则：当订单很重要且允许重复时，如果n是要选择的事物的数量(气球，数字等)，然后选择其中的r个(派对用5个气球，密码用4位数字)等)，排列的数量将等于P = n ^r 。

不允许重复的排列 (Permutations Where Repetition Isn't Allowed)

Next, let's consider the case where repetition is not allowed. As an example, we will look at the planets of our solar system.

接下来，让我们考虑不允许重复的情况。 例如，我们将研究太阳系的行星。

How many different ways can you arrange these 8 planets? The planets are: Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus and Neptune. After choosing, say, Mercury you can't choose it again. Thus, you have to reduce the number of available choices each time the planet is chosen.

您可以用几种不同的方式来排列这8个行星？ 行星是： 水星 ， 金星 ， 地球 ， 火星 ， 木星 ， 土星 ， 天王星和海王星 。 选择水星之后，您将无法再选择它。 因此，每次选择行星时，您都必须减少可用选择的数量。

The first choice will have 8 possibilities. The second choice will have 8 minus 1 equals 7 possibilities, then 6, followed by 5, followed by 4, until we have 1 planet left in the list.

首选将有8种可能性。 第二个选择将有8减1等于7个可能性，然后是6 ，然后是5 ，然后是4，直到列表中剩下1个行星。

Following the logic from the previous scenario, the total number of permutations is: P = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320.

按照上一场景的逻辑，排列的总数为： P = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320 。

In other words, this is a product of integer 8 and all the positive integers below it. This product is called Factorial and is denoted with an exclamation point, like this: 8!

换句话说，这是整数8和其下所有正整数的乘积。 此产品称为阶乘 ，并用感叹号表示，如下所示： 8！

The number of permutations equals P = 8! or more generally P = n!

排列数等于P = 8！ 或更一般地说P = n！

What if you only need to arrange, say, 5 out of these 8 planets instead of all of them? Then you only take the first 5 steps in our method. Namely, P = 8 x 7 x 6 x 5 x 4 = 6,720 will be how many ways you can arrange 5 planets out of 8.

如果您只需要在这8个行星中安排5个而不是全部，该怎么办？ 然后，您只需执行我们方法中的前5个步骤。 也就是说， P = 8 x 7 x 6 x 5 x 4 = 6,720将是您可以在8 个行星中排列5个行星的几种方式。

But why stop here? Why not apply our logic to come up with a more general formula? To make the above notation easy to remember for any numbers of objects, we will use a trick. In a fraction, multiplying both numerator and denominator by the same number (except zero), does not affect that fraction. Thus:

但是为什么在这里停下来？ 为什么不运用我们的逻辑来提出更通用的公式呢？ 为了使上面的符号对于任何数量的对象都易于记忆，我们将使用一个技巧。 在分数中，将分子和分母都乘以相同的数字(零除外)不会影响该分数。 从而：

Number of planets to choose from n = 8, you choose r = 5 of them. Substituting the numbers into above formula gives us P = 8! / (8 - 5)! = 8! / 3!. Same as 8 x 7 x 6 x 5 x 4 = 6,720.

要从n = 8中选择的行星数，请选择r = 5 。 将数字代入上式可得P = 8！ /(8-5)！ = 8！ / 3！ 。 与8 x 7 x 6 x 5 x 4 = 6,720相同 。

From here, the result from earlier example can be derived. There, you arranged all 8 out of 8 available planets. Using the new formula, P = 8! / (8 - 8)! = 8! / 0!. Since, factorial of zero is agreed to equal 1, P = 8! / 1 = 8!. Or more generally:

从这里，可以得出先前示例的结果。 在那里，您安排了8个可用行星中的所有8个。 使用新公式， P = 8！ /(8-8)！ = 8！ / 0！ 。 因为零阶乘被认为等于1 ，所以P = 8！ / 1 = 8!。 或更笼统地说：

P = n! / (n - n)! = n! / 0! = n!.  

P = n！ /(n-n)！ = n！ / 0！ = n！ 。

One short and convenient notation often used is: P(n, r) = n! / (n - r)!

经常使用的一种简短方便的表示法是： P(n，r)= n！ /(n-r)！

Remembering formulas is important. But what's more important for solving real life problems is to know which formulas to use in each situation. Practice helps.

记住公式很重要。 但是，解决现实生活中的问题更重要的是知道在每种情况下都应使用哪些公式。 实践会有所帮助。

Pop quiz:

突击测验：

Explanation: you have 6 teams to choose from. Thus n = 6. Gold and silver together give you 2 medals to award. Thus r = 2. Substituting these numbers into your formula gives us P(6, 2) = 6! / (6 - 2)! = 6! / 4! = 6 x 5 = 30.

说明：您有6个团队可供选择。 因此， n = 6 。 金牌和银牌一起给您2枚奖牌。 因此r = 2 。 将这些数字代入公式即可得到P(6，2)= 6！ /(6-2)！ = 6！ / 4！ = 6 x 5 = 30

第2部分。组合 (Part 2. Combinations)

无重复组合 (Combinations Without Repetition)

To make the comparison more vivid, let's revisit our planet selection example. What if you want to know just which planets are chosen and not their order of appearance?

为了使比较更加生动，让我们重新看一下我们的行星选择示例。 如果您只想知道选择了哪些行星而不是它们的出现顺序怎么办？

There you had 6,720 distinct ways of arranging 5 out of 8 planets. But since the order of appearance does not matter now, many of these ways are redundant. They are the same to us.

在那里，您有6,720种不同的方式来排列8个行星中的5个。 但由于出场顺序并不重要，现在，很多的这些方式都是多余的 。 他们对我们来说是一样的。

A group of Venus, Earth, Mars, Jupiter, Saturn is the same group as Mars, Jupiter, Venus, Earth, Saturn and the group as Saturn, Mars, Earth, Jupiter, Venus. These are just different sequences of the same 5 planets.

A 组金星，地球，火星，木星，土星的是相同的基团作为火星，木星，金星，地球，土星和组作为土星，火星，地球，木星，金星。 这些只是相同5颗行星的不同序列。

How many groups do you have that are the same? If you choose r planets per group, you get r! groups. For r = 5, you get r! = 5! = 120 groups.

您有多少个相同的小组？ 如果您每组选择r个行星，您将获得r！ 组。 对于r = 5 ，您得到r！ = 5！ = 120组。

Thus, to eliminate the unnecessary groups that are the same, you divide the number of original 6,720 Permutations by 5!. The result is 6,720 / 120 = 56.

因此，要消除不必要的组，请用原始的6,720个置换数除以5！ 。 结果是6,720 / 120 = 56 。

To generalize, in order to arrive at the number of Combinations, you need to figure out all the Permutations and divide by all the Redundancies.

概括地说，为了得出组合的数量，您需要找出所有排列并除以所有冗余 。

Using short and convenient notation: C(n, r) = P(n, r) / r! = n! / (r!(n - r)!)

使用简短方便的符号： C(n，r)= P(n，r)/ r！ = n！ /(r！(n-r)！)

And this assumes that order does not matter and there are no repetitions (that is – there is only one Jupiter to choose from).

而这个假设顺序并不重要，也没有重复(即-只有一个木星可供选择)。

Let's revisit the tournament example:

让我们回顾一下锦标赛示例：

As before, you have 6 teams. Thus, n = 6. There are two medals awarded, so r = 2. However, this time it doesn't matter who wins gold and who wins silver. Team gold and team silver is the same as team silver and team gold. Substituting these numbers into your formula gives us C(6, 2) = 6! / (2!(6 - 2)!) = 6! / 2! 4! = 15.

和以前一样，您有6个团队。 因此， n = 6 。 颁发了两枚奖牌，所以r = 2 。 但是，这次谁赢得金牌和谁赢得银牌都没有关系。 金牌和银牌与银牌和银牌相同。 将这些数字代入公式即可得到C(6，2)= 6！ /(2！(6-2)！)= 6！ / 2！ 4！ = 15 。

结合重复 (Combinations with Repetition)

To complete this article, there is one case that requires special attention. So far in our Combinations we assumed there was no repetition. No two items were the same.

要完成本文，有一种情况需要特别注意。 到目前为止，在组合中我们假设没有重复。 没有两个项目是相同的。

What if we can have repetitions? What if, as in our earlier example, we can choose more than one balloon of the same color? If the number of balloons to choose from is n and we choose r of them while allowing for same colors and disregarding the order of arrangement, we will end up with (n + r - 1)! / (r!(n - 1)!) Combinations.

如果我们可以重复呢？ 如果像我们前面的示例一样，我们可以选择多个同色气球，该怎么办？ 如果要选择的气球数量为n，并且我们在允许相同颜色且不考虑排列顺序的情况下选择了其中的r个 ，我们将得到(n + r-1)！ /(r！(n-1)！)组合 。

So wrapping up, here is a table you can use to reference these concepts and their formulas.

总结一下，这是一张表，您可以用来参考这些概念及其公式。

I hope this article has helped you better understand these two important mathematical concepts. Thanks for reading.

希望本文能帮助您更好地理解这两个重要的数学概念。 谢谢阅读。

翻译自:

java组合与继承始示例