70

4 项:

A
B
C
D

可能有 6 对独特的配对:

AB
AC
AD
BC
BD
CD

如果我有 100 个起始项目怎么办?有多少对独特的配对?有没有我可以把它放进去的公式?

4

4 回答 4

106

TLDR;公式是集合n(n-1)/2n的项目数。

解释:

要查找集合中唯一对的数量,其中这些对受交换属性 (AB = BA)的约束,您可以计算其中的总和1 + 2 + ... + (n-1)其中n是集合中的项目数。

推理如下,假设您有4个项目:

A
B
C
D

可配对的项目数A为 3,或n-1

AB
AC
AD

由此可知,可以配对的项目数Bn-2(因为B已经配对A):

BC
BD

等等...

(n-1) + (n-2) + ... + (n-(n-1))

这与

1 + 2 + ... + (n-1)

或者

n(n-1)/2
于 2016-06-15T23:33:35.460 回答
80

您正在寻找的是n 选择 k。基本上:

在此处输入图像描述

对于每对 100 件商品,您将有 4,950种组合- 前提是顺序无关紧要(AB 和 BA 被视为单个组合)并且您不想重复(AA 不是有效的组合)。

于 2013-09-17T20:39:49.770 回答
44

这是您自己解决这些问题的一般方法:

可以以 N (=100) 种方式选择一对中的第一个。您不想再次选择此项目,因此可以以 N-1 (=99) 种方式选择该对中的第二个。总的来说,您可以以 N(N-1) (= 100*99=9900) 不同的方式从 N 中选择 2 个项目。

但是等等,这样你也可以计算不同的顺序:AB 和 BA 都被计算在内。由于每对都被计算两次,因此您必须将 N(N-1) 除以 2(您可以订购两个项目列表的方式数)。那么你可以用一组 N 组成的两个子集的数量是 N(N-1)/2 (= 9900/2 = 4950)。

于 2013-09-17T22:21:41.647 回答
9

我正在解决这个算法并陷入配对部分。

这个解释对我有很大帮助 https://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/

所以要计算一系列数字的总和:

n(n+1)/2

但是你需要计算这个

1 + 2 + ... + (n-1)

所以为了得到这个,你可以使用

n(n+1)/2 - n

等于

n(n-1)/2
于 2017-06-01T05:38:10.977 回答