Sign in to follow this  
dev578

Trouble with an algorithm

Recommended Posts

dev578    128
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

Share this post


Link to post
Share on other sites
SiCrane    11839
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?

Share this post


Link to post
Share on other sites
deavik    570
Yes, it's a permutation problem--akin to 'arrange x objects in y*z places'. That's

y*zPx = (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*zPn

or something like that.

Share this post


Link to post
Share on other sites
dev578    128
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

Share this post


Link to post
Share on other sites
Forcas    181
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[i][j] == 0)
{
grid[i][j] = depth+1;
BackTrack(depth+1);
grid[i][j] = 0;
}
}
}
}
}

//main, or some other section of your code
int 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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this