Archived

This topic is now archived and is closed to further replies.

Gandalf

How many combinations?

Recommended Posts

How many combinations is possible for a 3x3 square grid, if the center square always is the same and the grid can be rotated 90, 180 and 270 degree but not fliped horizontaly or verticaly? Example: This one: x - - - C - - - - is the sam as: - - x - C - - - - - - - - C - - - x - - - - C - x - - But this is diffrent: - x x - C - - - - How many combinations viewed on the whole? I don´t know if I have every one and if I miss someone my BIG if-switch get fucked up!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
There are 64 combinations, because the center square was ruled out and for all other squares there exists 4 symmetrical points (you can rotate them 4 times 90 degrees to come back to the original configuration).

I don''t know if the 64 you have found are the correct ones, but I think so. But anyway, there should be 64 combinations from which you can form all 256 combinations by using rotates of 90, 180 or 270 degrees.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
No, for example

111
1x0
101

is the same as 2nd row, 2nd square in your picture rotated 180 degrees.

So you just probably haven''t found the correct 64 squares. If I were you I''d write a program that generates them.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
There is a way to calculate the possible number of combinations.

Look for Burnside''s lemma, Polya-Burnside or Polya''s enumeration theorem if you want to try analytically calculating the combinations. If I were you, I''d probably write a program to do that though.

http://www.aryankindred.com/sniffy/polya_burnside.html
had some stuff about Burnside''s lemma but if you really want to know this stuff, I''d recommend checking out some introductory combinatorial mathematics book.

I''d calculate the number for you, but unfortunately I don''t remember how the lemma was used. Haven''t actually needed it all that much after the combinatorics course

Share this post


Link to post
Share on other sites
Thank you very much!

I will take a look on those theorem...
About that console program... Is it something like this:

while(array < 64)
{
randomize 8 number between 0 and 1
add to array if the combination isn´t possible to
acomplize with a rotation.
}

[edited by - Gandalf on August 11, 2002 7:07:17 PM]

Share this post


Link to post
Share on other sites
Change your program to loop through all 256 possible combinations of zeros and ones (8 nested loops of 0 to 1, or a loop of 0 to 255 using bitmasks... whatever you find easiest), and then add each one to the array if it doesn''t match a rotated one that''s already in there. That way, you know you''ll find all the possible combinations.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Share this post


Link to post
Share on other sites
I get 70 combinations? Weird.

Here is the program:


    

#include <iostream>
#include <vector>

struct neighbore
{
int n[8];
};

std::vector<neighbore> g_kaCombArray;

using namespace std;

void Calc256Comb();
void RemoveRots();
void PrintToFile(bool bArrayFormat);

int main()
{
Calc256Comb();
RemoveRots();
PrintToFile(false);
return 0;
}

void PrintToFile(bool bArrayFormat)
{
FILE* pkFile = fopen("combinations.txt", "w+t");

for(int j=0; j<g_kaCombArray.size(); j++)
{
for(int d=0; d<8; d++)
{
fprintf(pkFile, "%i", g_kaCombArray[j].n[d]);

if(bArrayFormat)
{
if( d==2||d==4)
fprintf(pkFile, "\n");
else
if( d==3 )
fprintf(pkFile, "x");
}
}

fprintf(pkFile, "\n%i\n---\n", j);
}

cout << endl << endl;

fclose(pkFile);
}

void Calc256Comb()
{
while(g_kaCombArray.size() < 256)
{
neighbore new_apa =
{
rand()%2,rand()%2,rand()%2,
rand()%2,rand()%2,
rand()%2,rand()%2,rand()%2
};

bool bOk=true;

for(int j=0; j<g_kaCombArray.size(); j++)
{
if( g_kaCombArray[j].n[0] == new_apa.n[0] &&
g_kaCombArray[j].n[1] == new_apa.n[1] &&
g_kaCombArray[j].n[2] == new_apa.n[2] &&
g_kaCombArray[j].n[3] == new_apa.n[3] &&
g_kaCombArray[j].n[4] == new_apa.n[4] &&
g_kaCombArray[j].n[5] == new_apa.n[5] &&
g_kaCombArray[j].n[6] == new_apa.n[6] &&
g_kaCombArray[j].n[7] == new_apa.n[7])
{
bOk = false;
break;
}
}

if(bOk == true)
g_kaCombArray.push_back(new_apa);
}
}

void RemoveRots()
{
int iCombInProcess = 0;

for(int j=0; j<g_kaCombArray.size(); j++)
{
neighbore rotn = g_kaCombArray[j];

for(int r=0; r<3; r++)
{
bool bExit=false;
RotNumbers90deg(rotn);

for(int k=0; k<g_kaCombArray.size(); k++)
{
if( k==j)
continue;

if( rotn.n[0] == g_kaCombArray[k].n[0] &&
rotn.n[1] == g_kaCombArray[k].n[1] &&
rotn.n[2] == g_kaCombArray[k].n[2] &&
rotn.n[3] == g_kaCombArray[k].n[3] &&
rotn.n[4] == g_kaCombArray[k].n[4] &&
rotn.n[5] == g_kaCombArray[k].n[5] &&
rotn.n[6] == g_kaCombArray[k].n[6] &&
rotn.n[7] == g_kaCombArray[k].n[7])
{
g_kaCombArray.erase( g_kaCombArray.begin() + j );
bExit = true;
}

if(bExit == true)
break;
}
}
}
}

void RotNumbers90deg(neighbore &rn)
{
neighbore b = rn;

rn.n[0] = b.n[2];
rn.n[1] = b.n[4];
rn.n[2] = b.n[7];
rn.n[3] = b.n[1];
rn.n[4] = b.n[6];
rn.n[5] = b.n[0];
rn.n[6] = b.n[3];
rn.n[7] = b.n[5];
}



[edited by - Gandalf on August 11, 2002 8:14:12 PM]

Share this post


Link to post
Share on other sites
I trust your program...

I don''t think there''s any particular reaason to believe the whole 256/4 idea... that clearly does not hold up... so 70 is as good a number as any.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I checked out my combinatorics course material and calculated the number of combinations analytically. It is 70.

In case someone is interested, here is the outline of the solution:

Allowed operations are 4 rotations (0, 90, 180 and 270 degrees).
If we number the squares like this:

321
4 8
567

the corresponding permutations are:

0 degrees: (1)(2)(3)(4)(5)(6)(7)(8)
90 degrees: (1357)(2468)
180 degrees: (15)(37)(26)(48)
270 degrees: (1753)(2864)

These give the cycle index of:
(x_1^8 (for 0 degrees) + x_4^2 (90 deg) + x_2^4 (180 deg) + x_4^2 (270 deg)) / 4

which, leaving out the subscripts as they are not needed in this solution, simplifies to:
x^8 + x^4 + 2x^2
----------------
4

Then (I think this is according to Burnside''s lemma, but it can be derived from Polya''s method of enumeration too) we simply replace x with the total number of possible colors, giving:

(2^8 + 2^4 + 2*2^2) / 4 = (256 + 16 + 8) / 4 = 70

I also found a good hands on introduction with a lot of examples to Polya''s counting theory, so if you want to derive the result yourself, check:

www.geometer.org/mathcircles/polya.pdf


Share this post


Link to post
Share on other sites
Thank you very much sir! That was a comprehensive inquiry of the subject! Now I´m entirly convinced that it will go well to use this set of masks for my game. Now it´s time to start coding

Share this post


Link to post
Share on other sites
In a rpg tile engine I was working on a few months ago used a 16 combo based on binary numbers.

At first I was working with the 8 point system (like you guys), but figured out after a week that would take to long, so I started on this 4 point system. It uses only 16 total different tiles that can be supressed to this: and be loaded, rotated, and stored when a map loads. I ended up with 40+ pages of notes on tiles and spent a month on the math and finding the best method to have the editor choose tiles correctly. I got it working mostly, but there were some errors with using differnt types of land on other than grass. I gave up a few months ago to start on something new.
I can upload the last version of that editor to my site if you guys would like to see it.
I wish I found this site earlier! Would have save me tons of time to do things like homework and not nearly not graduating from HS.
[sorry about any grammer and spelling errors. my father is trying to get me away from the computer now.]
Josh

[edited by - simrct on August 14, 2002 12:12:01 AM]

Share this post


Link to post
Share on other sites
Here was how I numbered mine.
1--2
|--|
8--4

so tile 3 would be
1--1
|--|
0--0

and tile 5
1--0
|--|
0--1

and 14
0--1
|--|
1--1


My frist way was like this
1--2--4
128----8
64-32-16
but the number were quite high and made a very large number of tiles needed.


My idea was to take 3 numbers (shape, base color, transiton color, plus some others about the tile set), get one number that can be save to a map file, then load and use that number from an array and get 2 numbers (row,col.) from the tile set surface.


[edited by - simrct on August 17, 2002 4:23:22 PM]

Share this post


Link to post
Share on other sites