#### Archived

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

# 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 on other sites

Because no-one seems to understand my question, here is a
picture of all combinations I can think of:

Can you find more combinations?

##### Share on other sites
Surely there should be 256 combinations, as you have 8 squares which can be in one of 2 states, meaning 2^8 = 256.

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

##### Share on other sites
I can''t really do this for you right now but you should write a short dos program that calculates this for you.

---
My Site
Come join us on IRC in #directxdev @ irc.afternet.org

##### Share on other sites
Kylotan: It can´t be 256 combinations! You forget that I can rotate each square 90, 180 or 270 degree.

##### Share on other sites
Hum... 256 combinations, 4 angles... 256/4 = 64... Maybe I have found them all?

##### Share on other sites
You already made that diagram; that is exactly all the possible combinations. Make 3 copies of that diagram at 90'', 180'', and 270'' rotations, and you have every possible combination.

##### Share on other sites
OK, I know now (thanks to Kylotan) that it is 256 combinations,
but how much smaller can I make that number if I can rotate each square 90'', 180'' or 270 degree?

##### Share on other sites
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 on other sites
Thank you man!

That was all I wanted to know

##### Share on other sites
no! I found 2 other combiantions

111
1x0
101

111
1x1
111

fuck...

I will never find them all

##### Share on other sites
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 on other sites
No that is,

000
0x1
010

(it´s not allowed to invert squares)

##### Share on other sites
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 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 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 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 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 on other sites
Thank you Pyabo... but I´m still not sure.

Here is the 70 combinations.

##### Share on other sites
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 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 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 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 on other sites
Here is a picture of my terrain mask in progress...

Looks nice ? :=

[edited by - Gandalf on August 19, 2002 7:46:35 PM]

• ### Forum Statistics

• Total Topics
628312
• Total Posts
2981998

• 9
• 9
• 13
• 11
• 13