In n-dimensional grid (Max. 10^7 dimensions) are two points. They have imaginary sensors on every axis. I need algorithm what will calculate all possible options when these two points can spot themselves.
Formal written from my task document (translated to english):
Let A with the coordinates (a1, a2, ..., an) and B with the coordinates (b1, b2, ..., bn)
are two points in n-dimensional space and exists i ∈ 1, 2, ..., n such that ai = bi then A and B sees each other
Example:
In 1-dimensional space with length 10 is total 45 combinations how to put 2 points when they see each other (They see each other every time).
It is easy combination 10C2 (10 of 2) = 45
How to calculate it in 2,3,4,...,10^7 dimensions by program (I prefer C#)?
Proper test data what i have:
Input:
1
10
Output: 45
Input:
2
5 8
Output: 220
Input:
3
8 12 11
Output: 14784
More explanation:
Output is number of combinations when two points in space see each other (are on same axis). In 1 dimensional space is only one axis so they see each other always. In 2 dimensional space are 2 axis, so they can see each other only in some case
I'm sure it's correct.
C(x,y) is combination x of y.
Lets say we have one dimention, lets call it X of lenght 8. There are C(8,2) = 8*7/2 = 28 possibilities to see eachother.
When we add second dimention, named Y, of lenght 12 now we have 12 lines parallel to X. So we have 12*28=336 possibilities to being found on all the lines parallel to X. Now, on Y dimention we have C(12,2) = 66 possibilities. And there are 8 lines like that so 66*8=528.
In total: 336 +528= 846 possibilities
Now lets add another dimention, labeled as Z with lenght of 11. There are C(1,2) = 11*10/2 = 55 in one line and (atention) we have 8*12 lines like that. So is it's 55*8*12 = 5280 possibilities!
Now in total we have:
Paralel to X axis: C(8,2)*11*12 = 3696
Parallel to Y axis C(12,2)*8*11 = 5808
Parallel to Z axis C(11,2)*8*12 = 5280
TOTAL = 14784
In general the formula for n dimentions with n1,n2... nk lenghts is:
Sum of C(ni,2) * (n1*n2...*nk)/ni
Or shorter:
sum of (n1*n2*n3...nk)/2 * (ni-1)
example:
dimentions with 3,8,9,11:
(3*8*9*11)/2*(3-1) = 2376
(3*8*9*11)/2*(8-1) = 8316
(3*8*9*11)/2*(9-1) = 9504
(3*8*9*11)/2*(11-1) = 11880
Total = 32076
The easiest equasion:
(n1*n2*n3...ni)(n1+n2+...ni - k)/2, where ni are lenghs, and k is number of dimentions
