First of all, I want to say I wasn’t sure if I should post this here or in math.stackexchange but I think the question is too programming-related to belong to the latter community. Definetly not a SO question, though.
A brief introduction of my program: I am developing a scheduler for sport events using CSP. Each event can have different categories, for example, in a tennis event you could have a men’s draw, a women’s draw and a doubles’ draw. In a football tournament you could have group A, group B, group C… In the tennis event though, we can have players playing in different categories simoultaneously. My solver has that in mind.
For a specific purpose, I need to track which match-up combinations have already been tried. For a “match-up combination” we understand a specific combination of predefined match-ups between players. For example, in the tennis tournament, a specific combination could be:
Men's draw -> [Man1, Man6], [Man3, Man5], [Man2, Man4]
Women's draw -> [Woman3, Woman4], [Woman6, Woman2], [Woman1, Woman5]
Double's draw -> [Man6, Woman4, Woman1, Man3], [Man2, Man1, Woman2, Woman5],
[Man4, Woman3, Woman6, Man5], [Man7, Woman8, Woman7, Man8]
(I think haven’t missed any combination, but I hope you get the idea)
This combination is created from a pool of players defined for each category that composes the tournament. The following represents all players that play in each category:
Men's draw -> [Man1, Man2, Man3, Man4, Man5, Man6]
Women's draw -> [Woman1, Woman2, Woman3, Woman4, Woman5, Woman6]
Double's draw -> [Man1, Man2, Man3, Man4, Man5, Man6, Woman1, Woman2,
Woman3, Woman4, Woman5, Woman6, Man 7, Man8, Woman7, Woman8]
If the resolution process doesn’t work for a specific combination, which has been generated randomly, we go ahead and try with anothe randomly generated combination. We repeat until we find a solution.
Now, keeping track of the visited combinations would mean a huge cost in memory usage, because of all the information to be stored. I doubt the memory in a regular PC can handle the amount of combinations in a moderatly big tournament.
I think the proper way of doing this is, instead of storing the whole combination, we can store an integer representing a unique combination.
So, for example, the combination above maps to the integer 1, and so on. We could easily store set of integers. And for the next combinations we could check the identifier of the generated combination with the contents of that integet set to see if it has been already visited.
However, I can’t think of an algorithm to represent a combination with a unique integer. Could this be done? Is it easier to do than it sounds? Is it a good idea at all to do what I am suggesting?
Representing a combination of two values takes as many bits as representing those two values, added together. If your “players” are represented as 32-bit integers, you can have 2^32 of them.
Whether you should store attempted combinations as actual integers (making use of the bit representation encoded into your programming language) or as raw bits (if your programming language has bit fields built in) depends on what is more efficient to program and run in your particular environment. Either way, read up on bitwise operations, particularly bit shifts, to learn how to store two values in one larger value.
(Note that if the order of a match-up doesn’t matter – O’Sullivan playing Higgins is equivalent to Higgins playing O’Sullivan – then technically you need one less bit, but it’s probably not worth to invent a more space efficient storage scheme because it’s more complicated to implement.)
1