在二維數組中找到唯一的相鄰索引

假設我有一個二維數組對象，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

在二維數組中找到唯一的相鄰索引

回答

相關問題