1

假设我有一个二维对象数组，N x N。假设一对可以由水平、垂直或对角的每一对相邻的对象组成。对于任何 N 值，我如何计算有多少个唯一对？

例如对于 N = 2

0 1
2 3

可以得到01 02 03 21 23 31，注意03和30一样

是否有一个公式可以确定给定 N 有多少对，甚至更好的算法来生成这些对？

语言不是那么重要，但我将使用 c++。

使用以下算法并消除重复索引，我得到以下计数。不知道公式是什么。

For size N=2
Unique pairs is =6
For size N=3
Unique pairs is =20
For size N=4
Unique pairs is =42
For size N=5
Unique pairs is =72
For size N=6
Unique pairs is =110
For size N=7
Unique pairs is =156
For size N=8
Unique pairs is =210
For size N=9
Unique pairs is =272

有趣的是，公式似乎是 2^2+2, 4^2+4, 6^2+6, 8^2+8 ...

4

3 回答 3

1

我发现选择每种类型对的代表对象最容易（换句话说，垂直对的顶部对象，水平对的最左侧，然后选择对角线对）。这给出了n(n-1)垂直对、n(n-1)水平对和2(n-1)^2对角对（每个品种的数量相等）。与您的猜测2(n-1)(n+n-1)=2(n-1)(2n-1)一致。

于 2013-10-17T03:33:50.190 回答
1

每行有 n-1 个行内对，并且有 n 行。

每列有 n-1 个列内对，并且有 n 列。

每对相邻的行有 2*(n-1) 个对角线对，并且有 (n-1) 个相邻的行对。

将这些数字相乘并相加，您将得到解决方案。

于 2013-10-17T04:20:00.640 回答
0

这是计算唯一对的固定公式。

(4 C 2)*(N-1)^2 - 2*(N-2)*(N-1)

基本上，您只需使用 dasblinkenlight 的答案中的方法并减去“重复”边缘。重复的边总是象限之间的边。我在下面添加了对重复计数的解释。

对于 N > 2，使用原始公式 (4 C 2) * (N-1)**2，您将计算重复项。您要做的是从计算中减去这些重复的边。

让我们检查 N > 2 的最简单情况。假设 N = 3。

0-1-2
|x*x|
3*4*5
|x*x|
6-7-8

看到我标记星号而不是边缘的地方了吗？这些边将被公式计算两次。我们可以通过将它们分解为水平和垂直边缘来计算它们。计算两次的垂直边数将为(N-2)*(N-1)。在 N=3 的情况下，这将是1 * 2 = 2。被计数两次的水平边数也将是(N-2)*(N-1)。

因此，如果我们简单地将重复的垂直边和重复的水平边的数量相加，我们得到

(N-2)*(N-1) + (N-2)*(N-1) = 2*(N-2)*(N-1)

我们可以简单地从总数中减去该数字以获得正确的边数。

Python中的测试计数：

from math import factorial

def choose(n, k):
    return factorial(n)/(factorial(k) * factorial(n-k))


for N in range(2, 10):
    print choose(4, 2) * (N-1)**2 - 2 * (N-2) * (N-1)

程序打印：

6
20
42
72
110
156
210
272
于 2013-10-17T03:32:32.417 回答