1
$\begingroup$

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}.

I need to to know how many K-sets exist(here K-set refers to set of points whose distance between 2 points of set is K).But as there can be infinite number of these K-sets. Thus, we would only like to count the number of classes of K-sets, such that any two K-sets which belong to the same class are equivalent if they follow given conditions.Two K-sets X and Y are considered equivalent (and belong to the same class) if:

They contain the same number of points 
There exists N integer numbers (t1, ..., tN) such that by translating each point of X  
 by the amount ti in dimension i (1≤i≤N) we obtain the set of points Y.

Let's consider N=2, K=4 and the following sets of points X={(1,2), (5,5), (4,3)} and Y={(2,5), (5,6), (6,8)}. Let's consider now the tuple (1,3). By translating each point of X by the amounts specified by this tuple we obtain the set {(2,5), (6,8), (5,6)}, which is exactly the set Y. Thus, the two sets X and Y are equivalent and belong to the same class.

Example let say N=2 and K=1 .

There are 9 classes of K-sets. One K-set from each class is given below:

{(0,0), (0,1)}
{(0,0), (1,0)}
{(0,0), (1,1)}
{(0,1), (1,0)}
{(0,0), (0,1), (1,0)}
{(0,0), (0,1), (1,1)}
{(0,0), (1,0), (1,1)}
{(0,1), (1,0), (1,1)}
{(0,0), (0,1), (1,0), (1,1)}

So answer here will be 9.

$\endgroup$

closed as unclear what you're asking by Raphael Feb 12 '14 at 9:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ So what's your question? I don't see any question in the above. Are you looking for an algorithm? to compute what? What's the input to the algorithm, what's the desired output? Will any correct algorithm do, or do you have performance requirements? What have you tried? We expect you to make a serious effort to solve your own problem before asking here, and to show us what you've tried in the question. $\endgroup$ – D.W. Jan 13 '14 at 7:42
  • $\begingroup$ @D.W. The question is i want to find the count of these K classes.Yeas i am looking for its algorithm and input will be N and K where both N is upto 1000 and K can be of range 10^9 $\endgroup$ – user3001932 Jan 13 '14 at 7:55
  • $\begingroup$ OK, I suggest you edit the question to reflect that additional information, and to end by asking a specific question. "I want to find.." is not a question. "What is an algorithm to find..?" is a question. "What is the optimal algorithm to find..?" is another, different question. Make sure you know what you're asking, and write it in the question -- don't force us to guess. $\endgroup$ – D.W. Jan 13 '14 at 9:26
  • $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Feb 12 '14 at 9:15
1
$\begingroup$

I'm going to assume that the problem is to devise an algorithm to count the number of equivalence classes of $K$-sets on $\mathbb{Z}^N$, given $K,N$ as input.

To help us count them, let's pick a canonical representative for each equivalence class. One way to do that is to pick the $K$-set that contains the point $(0,0)$: the equivalence class must contain exactly one such set, so it can be used as the canonical representative.

So now the problem becomes:

Given $K,N$, count the number of sets of points from $\mathbb{Z}^N$ that contain the point $(0,0)$ and such that every pair of points in the set is at distance exactly $K$ from each other (using the $L_\infty$ distance).

Computing this is pretty straightforward. Suppose that $S_1,\dots,S_m$ is the list of all such sets of size $s$. For each $S_i$ and each $x \in S_i$, there are $N$ possible points $y$ that are at distance $K$ from $x$; enumerate them all. Then, for each such $S_i,x,y$, test whether $y$ is at distance $K$ from all other points of $S_i$ and whether $y\notin S_i$; if both conditions hold, then $S_i\cup \{y\}$ is a valid set of size $s+1$. Continue in this fashion, enumerating first all sets of size $1$, then all sets of size $2$, then all sets of size $3$, etc., until no more can be found.

The running time of this algorithm will be at most $O(nNs)$, where $n$ is the total number of such sets (equivalence classes), and $s$ is the maximum size of any such set.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.