Need urgent help in writing an algorithm

Hi everyone,

I am new to this forum and it seems to be very good one. I am in a position to write an algorithm in a short time and since I haven't done any programming for the last 2 to 3 years, i need any of your help. Below is the scnario:

There is an array (100 rows X 6 cols) with string elements of X, Y, Z and U. These elements are randomly spread out in the array. The algorithm is supposed to search the array to connect X to X, Y to Y and Z to Z. And it shouldn't pair up with U (you can take U as garbage, have to avoid). The output is a file (an excel file) that should give the location of the pair. The critical part is that we should connect to the closest one. For example, say array[0,0], array[0,1] and array[3,5] all consist of X. The algorithm should pair up array[0,0] with [0,1].

I think I have said enough, but if it doesn't make sense or you want to do any assumption, go ahead and do it.

Thanks in advance,
macsp

can you say, for example how many of each of X, Y and Z in the matrix - and how many pairs you want recorded.

thanks for your intention to help me. To answer your question, the number of X,Y and Z is not defined, it can be in any amount. Say we have 21 X es, obviously we can pair up 10 and leave the one.

macsp

ok - and am i right to think the the ten pairs chosen should be such that the total distance between the items of the pairs is as small as possible?

how do you calculate distance?

is something that considers all possible pairs acceptable or does it miss the point?

you are right. the distance should be as small as possible. however, the priority goes for the smallest distance. that means if you don't have a pair close, then you can pair with the one that is far instead of leaving it alone unpaired. in my case, you shouldn't worry about the number of X, Y and Z. I just need the algorithm to search (say in all 8 directions) and find the pair in an array. the distance can be calculated from the cordinates with Pythagrom theary ( d=sqrt(x2-x1)square + (y2-y1)square ) ).

thanks

here's a thought, not sure how efficient it would be, but: go thru the entire array once, any x,y,z value found would have it's position in the array stored into a node on a linked list. x,y, and z would each have their own linked list. the node data members would be x,y, and the next pointer. at least this way u only need to traverse the array once. then u could write a method for the listclass that would sort the nodes according to proximity of each other, by this i mean: the first two nodes would be a pair, then the next two would be a pair, etc... im tryin to think of the algorithm to do that right now, i'll get back to u soon.

ok, how does this sound, assuming that u take my advice and create linked lists like i said in above post. here is is:

-list class would need a member that kept track of the number of nodes
-node would need an additional data member, an array of ints representing the distance between itself and the other nodes. the array would need to grow, perhaps a vector would be a better idea? to explain this clearer, lets say there are 3 nodes in list: node 1 would have an array like this, distArray{dist to itself, dist. to node 2, dist. to node 3}, then node 2 array, distArray{dist. to node 1, dist. to itself, dist to node3}, node 3 array distArray{dist. to node1, dist. to node2, dist. to itself}
-the measuring of distances would occur when u insert the node into the list. assuming the node being inserted is not the first node, something like this:

addNode(node *ptr)
{
numNodes++;
node *tmpPtr = head;
node *curPtr = ptr;
int x = 0;
while(tmpPtr->next != NULL&& x<numNodes)
{
val = distance between tmpPtr and curPtr;
tmpPtr[numNodes-1] = val;
curPtr[x] = val;
x++;
tmp = tmp->next;
}
//here u need one more loop for the final node not done(when tmpPtr->next == NULL)
//then set curPtr[x] = 0 as this will represent the distance to itself!
//then attach curPtr to the list
now u have all the distances stored in the arrays. so if there is an odd number of nodes, first thing to do is eliminate the further node, this can be calculated by summing the elements in the array of each node, the largest total is the furthest away and can be eliminated.
- then start with the first node's distance array, find the smallest value in that array(besides 0 of course)
-move to the next node's array. u need to compare 2 things here, 1)to see if u can match the value from the previous step and 2)to make sure that value isnt larger than any values in the current node, as that would mean this node has another node that is closer to it.
-rinse and repeat
-the good thing about this is that u never have to calculate the same distance twice! this was what i was trying to work around.
-however there are still some holes, like how to deal with even distances, how to remove a pair from searching once u have made a match for it, prolly some more things i cant think of. hope that helps a bit. tell me if u come up with something better,this stuff interests me alot!!

HI infamous41md,

thanks for your help here. I will take your advice and try out soon. if I have any questions or concerns, I will let you know.

again, thanks a lot and I really appreciate your help.

macsp