在二维数组中找到唯一的相邻索引

假设我有一个二维数组对象，N×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 ...

来源

2013-10-17 ahwulf

下面是用于计数的固定式独特的配对。

(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)

该程序打印：

来源

2013-10-17 03:32:32 Shashank

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

来源

2013-10-17 03:33:50 Teepeemm

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

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

每一对相邻的行都有2 *（n-1）对角线对，并且有（n-1）个相邻的行对。

乘以并添加这些数字，你会得到你的解决方案。

来源

2013-10-17 04:20:00 ElKamina

在二维数组中找到唯一的相邻索引

回答

相关问题