dev578 128 Report post Posted December 4, 2005 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 0 Share this post Link to post Share on other sites
SiCrane 11839 Report post Posted December 4, 2005 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? 0 Share this post Link to post Share on other sites
deavik 570 Report post Posted December 4, 2005 Yes, it's a permutation problem--akin to 'arrange x objects in y*z places'. That's ^{y*z}P_{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*z}P_{n}or something like that. 0 Share this post Link to post Share on other sites
dev578 128 Report post Posted December 4, 2005 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 0 Share this post Link to post Share on other sites
Forcas 181 Report post Posted December 4, 2005 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 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] 0 Share this post Link to post Share on other sites