CODEWITHSUNDEEP
arraysalgorithm2d
ahwulf
ahwulf

Reputation: 2584

find unique adjacent indices in 2d array

Assume I have a 2d array of objects, N x N. Assume that a pair can be made of every adjacent pair of objects, horizontally, vertically or diagonally. How can I count how many unique pairs there are for any value of N?

For example for N = 2

0 1
2 3

You can get 01 02 03 21 23 31, note that 03 is the same as 30

Is there a formula to determine how many of these pairs there are for a given N, and even better an algorithm for generating these?

Language is not that important but I will be using c++.

Using the below algorithm and eliminating duplicate indices, I get following counts. Not sure what the formula is yet.

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

Interesting, the formula appears to be 2^2+2, 4^2+4, 6^2+6, 8^2+8 ...

Upvotes: 1

Views: 426

Answers (3)

ElKamina
ElKamina

Reputation: 7807

Each row has n-1 intra-row pairs and there are n rows.

Each column has n-1 intra-column pairs and there are n columns.

Each adjacent pair of rows have 2*(n-1) diagonal pairs and there are (n-1) adjacent row pairs.

Multiply and add these numbers and you will get your solution.

Upvotes: 1

Shashank
Shashank

Reputation: 13869

Here's the fixed formula for counting unique pairs.

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

Basically you just use the approach in dasblinkenlight's answer and subtract the "duplicate" edges. The duplicate edges will always be the edges between quadrants. I've added an explanation for the counting of duplicates below.

Using the original formula (4 C 2) * (N-1)**2 for N > 2, you will count duplicates. What you want to do is subtract these duplicate edges from the calculation.

Let's examine the simplest cases for N > 2. Suppose N = 3.

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

See the places where I marked an asterisk instead of an edge? Those edges will be counted twice by the formula. We can calculate them by breaking them up into horizontal and vertical edges. The number of vertical edges that are counted twice will be (N-2)*(N-1). In the case of N=3, this will be 1 * 2 = 2. The number of horizontal edges that are counted twice will also be (N-2)*(N-1).

So if we simply add up the number of duplicate vertical edges and duplicate horizontal edges, we get 

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

We can simply subtract that number from our total to get the right number of edges.

Testing count in 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)

The program prints:

6
20
42
72
110
156
210
272

Upvotes: 0

Teepeemm
Teepeemm

Reputation: 4508

I find it easiest to pick a representative object of each type of pair (in other words, the top object of a vertical pair, the left most of a horizontal pair, and take your pick for diagonal pairs). This gives n(n-1) vertical pairs, n(n-1) horizontal pairs, and 2(n-1)^2 diagonal pairs (equal amounts of each variety). That totals up to 2(n-1)(n+n-1)=2(n-1)(2n-1), in agreement with your guess.

Upvotes: 1

Related Questions