[gameprogrammer] Re: Let's play... Name That Algorithm! :)

  • From: Kevin Jenkins <gameprogrammer@xxxxxxxxxx>
  • To: gameprogrammer@xxxxxxxxxxxxx
  • Date: Tue, 18 Aug 2009 08:10:07 -0700



niyoto@xxxxxxxxxx wrote:
Hi Kevin - thanks for your responses! I'm going to try your Working List / Completed List idea to see how it fits. :)

As for the combinations:

    0  1  2  3
0 [*, 1, 0, 1]
1 [*, *, 1, 1]
2 [*, *, *, 0]
3 [*, *, *, *]

Using the same truth-table as before - the "truth" in this case is that unit 0 is compatible with units 1 and 3. Unit 1 is compatible with units 2 and 3. My goal is to determine all possible combinations of units 0, 1, 2 and 3 where each unit is compatible with each other unit. Thus 0-1-2-3 is not a possibility because 0 and 2 are incompatible. As are 2 and 3.

My optimal solution would be a set of all combinations of the three - and thinking further, it's best that I also exclude any combinations which are simply sub-sets of longer combinations (ie. if I have 0-1-3 as a combination I'd prefer to exclude 0-1 and 0-3 as reported results).

I didn't look at the code you posted, but what you describe here is exactly the algorithm I described. You are trying to find the minimum number of graphs needed to represent your set, where every vertex is connected to every other vertex. To do that, build graphs by adding vertices as long as the new vertex can connect to all existing vertices.

---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html


Other related posts: