Reputation: 2665
here is what I mean:
Assuming we have X number of colours and a 4x4 grid of 16 squares, we can colour any of the squares with any colour.
Assuming you can generate a list of all possible configurations and the algorithm spits them out one after another(configuration#1
, then configuration#2
and so on), is there a way to use a number i
and get configuration#i
right off the bat?
(since storing 1e+16 configurations is not possible on normal hardware)
And more importantly, is it possible to have an inverse of this algorithm and to instead give it a configuration, for which it will return an i
that when plugged back in will return the original configuration? Something like this:
int colours[4][4] = GenerateSomeConfig(); // Gets some combination of colours
int i = GetIndex(colours); // This is the main function I was asking about
int colours2[4][4] = GetConfig(i); // This is the reverse of GetIndex()
assert(CompareGridsEqual(colours, colours2)); // This shouldn't break
Upvotes: 1
Views: 103
Reputation: 1352
As I said in the comment, it is possible for every algorithm that generates the configurations to create a wrapper that converts a configuration to integer and vice versa.
The simplest and general solution would be like this:
config_t GetConfig(size_t index)
{
Generator gen;
for(size_t i = 0; i < index; ++i) gen.GetNextConfig();
return gen.GetNextConfig();
}
size_t GetIndex(const config_t & conf)
{
size_t ret = 0;
Generator gen;
while(gen.GetNext() != conf) ++ret;
return ret;
}
This is obviously not very efficient way of doing it, but it shows that it's possible. If you need to do it more efficiently you'll probably have to sacrifice generality and implement it specifically for the one generator. @luk32's answer shows you the way of doing it for a very simple generator, but of course there can be more complex generators.
Upvotes: 1
Reputation: 16080
Those are combinations with repetition.
Anyways. Let's simplify problem just a little bit. Let us say we have 10 colours. Numbered 0 to 9. Lets also number our squares, from 1 to 16 (or whatever. You say 4x4, your code says 16x16 but it's not important).
You can use the number of the color of the box. So you would end up with lets say:
0 9 6 3
4 7 5 1
0 2 1 7
5 2 3 4
Now you can take the grid, and make it a stripe - 0 9 6 3 4 7 5 1 0 2 1 7 5 2 3 4
. Remove spaces and you have your mapping.
To use different number of colors, use different base. Different size of grid will result in different number of digits in the encoded number.
You should be able to take off from this hint. I'm not going to write a c++ implementation to match your effort =P, and I think you should be able to do it. The only technical difficulty is to deal with numbers of arbitrary base.
Upvotes: 5