🔒 Locked

Trouble with an algorithm

Started by dev578 Dec 4, 2005 at 10:35 AM 3 replies 650+ views

Original Post

Dec 4, 2005 at 10:35 AM

What I am trying to implement here is an algorithm that can place x dots on a y by z grid, in all possible combinations that they can be. The dots are labeled 1 through x+1. (x, y, and z are constants) A few additional specifications are that if dot 1 is placed at (0,1) and dot 6 is placed on (5,6); and in another instance if dot 6 is placed on (0,1) and dot 1 is placed on (5,6), then they are TWO different combinations. Additionally, two dots cannot be placed on the same point. This probably sounds ridiculous, but I am doing this to try to solve for all possible combinations in a game I am making, so I can solve my game, in a sense. I don't really even know where to start, I would assume it would be a large nested for loop mess, but I really can't think of anything that would work. If anyone could help me out, that would be greatly appreciated. I know this is hard (for me anyway), so definately rating++ to someone who helps. Thank you, Dev578

SiCrane

Mod

473

SiCrane

Dec 4, 2005 at 10:40 AM

As near as I can tell, the number of different permutations you have is (y * z)!/(y * z - x)! This can be a really, really big number. Are you sure you need to find all the permutations?

deavik

Dec 4, 2005 at 10:45 AM

Yes, it's a permutation problem--akin to 'arrange x objects in y*z places'. That's

^y*zP_x = (y*z)! / (y*z - x)!

as SiCrane mentioned. By the way, if the dots are labelled 1 through x+1 that makes x+1 dots in total. Just wanted to warn you, in case you plan to put that on the cover of the box of your game. [lol]

/edit: An important thing I forgot to mention--this assumes that all the dots are actually placed on the grid. If the number of dots placed is variable, then you are in an even bigger soup.

Total permutations = SUM _{(n = 0 to x)} ^y*zP_n

or something like that.

dev578

Author

dev578

Dec 4, 2005 at 11:11 AM

Thank you, now that I know what it is called, I found a few articles on it that I am reading through. FYI, this is not going to be part of the game, it is separate, just so I can calculate all the possibilities and spit out the best solution. And yes, I understand that this will take awile to iterate through:) Rating++, and thank you.

Dev578

Forcas

Dec 4, 2005 at 11:18 AM

Assuming x,y, and z are reasonable, you can use a recursive backtracking algorithm to generate all placements.

int grid[y][z];void BackTrack(int depth){   if(depth == x)   {      //a solution has been found   }   else   {     for(int i = 0; i < y; ++i)     {       for(int j = 0; j < z; ++j)       {         if(grid[j] == 0)         {           grid[j] = depth+1;           BackTrack(depth+1);           grid[j] = 0;         }       }      }   }}//main, or some other section of your codeint main(){  intialize grid to all 0's  BackTrack(0);  return 0;}

As has already been said, this task quickly becomes too large. If I knew more about your game, I may be able to give a better solution.

[Edited by - Forcas on December 4, 2005 6:18:12 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.