Thread: algorithm hint needed. please.

Note that "Not Mirrored" is the same position as "Rotated 0 degrees", so 16 is highly suspect.

Adak for your previous post:

Think of the image to be drawn over a transparent material. So I wanna see it from the back as well.
Actually that is what I am going to do tonight. If time permits. I will get some transparent material to draw
on and will draw some bitmaps by hand on them. And will see how many combinations I can get!
But it will be really lame way of doing this I think

So when you flip a bitmap image over, it will display just like the front side, in a different orientation.

I think humans are pretty crafty when doing work by hand. Lazy maybe, but efficient. I don't think you
need to draw out the whole bitmap. Just a 10 X 10 grid with an unbalanced position of dots should
be enough to help you.

Code:

If anybody knows Permutation-Combination maths then please help me find total number of combinations here:
Rotations: 1 2 3 4
Flips : H V
Mirrors: U D R L

So,
I can have a rotation in any of the 4 ways (1,2,3 or 4).
I can have flips in any of the 2 ways (Horizontal, Vertical).
I can have mirrors in any of four ways (Up, Down, Right, Left).
My combinations can be thought of strings containing chars from { 1,2,3,4 }, { V, H } and { U, D, R, L}
So the operations on the bitmap can be thought of the strings representing one or more chars from above sets.
eg:
1
1V
1VU
1V4
1VL2
...
so on.
I think it's possible if you know Permutation-Combination to find exact number of cases.
Thanks!

PS: Don't know why? But while posting this I was asked to put code blocks by showing me an error dialog!

Thanks matsp.

This is not my home work.
Neither it is needed at my work.
Neither it is for any contest or as such.
I just got this stupid idea while thinking about how to solve N - Queens problem.
While thinking this problem I realized that out of (maybe 92 solutions for 8x8 standard chess)
all the outputs most were just a rotated/mirrored/flipped versions of the previous.
So I was thinking about filtering those outputs. This new idea then grew upon itself and I was
thinking about identifying bitmaps ...

I have the permutation equation in my permutation program on another computer. It won't help you, though. It doesn't take geometric movements into consideration. That's the key thing for us.

I don't know how you can say 4 * 4 when clearly the "unflipped" position, is the same as the "rotated 0 degree's" position.

It may interest you to know that the End Game Table Bases for Chess programs very famously uses all kinds of mirrored, rotated, & flipped positions, in order to decrease the permutations that have to be 1) calculated and 2) stored. (Nothing upside down, of course).

Here's something I didn't expect:

Take a 3X5 card and poke some unique and asymmetrical holes in it. Now, say you're ready to do the 4 different positions which arise from every base position.

1) Vertial Flip, 2) Horizontal Flip, 3) Negative 45 degree axis flip and turn, and 4) Positive 45 degree asix flip and turn.

Let's look at #3, -45 degree axis flip and turn. Hold the card by the upper left corner with your left hand, and the lower right corner with your right hand, and flip it over, using those two holding points as pivots.

Surprise - now the card is oriented along the long diagonal, and neither has the long side or the short side of it's rectangle, parallel with what it was, before the flip.

So a turn must be made to "square it up". And that could be either a 45 degree turn clockwise, or a 45 degree turn counter-clockwise.

Both the flip and turn positions, have this new option, so there are now more than 16 positions, BUT some of the positions are exact duplicates of others, even down to their orientation in a rectangle whose sides are always vertical, and whose top and bottom lines, are always horizontal.

If we're accepting 45% angled rectangles or squares, then it's a bigger kettle of fish!

To be continued...

This thread is probably dead by now, but I'll just reply for the heck of it...

Case 1: Square

I'll take matsp's convention of having:
A - 0 degree rotation clockwise
B - 90 degree rotation clockwise
C - 180 degree rotation clockwise
D - 270 degree rotation clockwise
AND
X - Unflipped
Y - Vertical flip (Top swaps with bottom)
Z - Horizontal flip (Left swaps with right)
W - Both flips have occured

It should be noted that (as has been previously said) A=X, but crucially also,
C=W. In order to form a group (mathematical term) however, we still need
two transformations, exactly the ones Adak was talking about, but still with a
square. We will call these two transformations S (top right corner swaps with
bottom left one) and T (top left corner swaps with bottom right one).

The following table shows the results of using two of the above transformations
after one another. First the transformation labelled at the top is done then the one at the side.

Table:
*|A B C D T Y S Z
-+----------------
A|A B C D T Y S Z
B|B C D A Y S Z T
C|C D A B S Z T Y
D|D A B C Z T Y S
T|T Z S Y A D C B
Y|Y T Z S B A D C
S|S Y T Z C B A D
Z|Z S Y T D C B A

e.g. C*Y=Z (check from table)
Note that when you perform two geometric transformations after one another
then the result is always the same as another (single) transformation(X). This
in turn means that however many transformations you perform you will always
end up with A,B,C,D,T,Y,S or Z. This means that there are exactly 8 permutations
of the original image subject to the 8 transformations.

Just FYI:

1. From (X), we can say that the set of transformations E={A,B,C,D,T,Y,S,Z}
   is closed under the operation of performing the transformations successively
   (That is, the operation *). (If there was a shorter way of saying that last
   part I couldn't think of it! ;-) )
2. There exists an identity transformation in E.
3. Every element in E (each transformation) has an inverse, which can be
   seen from the table above.
4. It can also be seen from the table that the operation of performing the
   transformations successively is associative. This simply means that if we
   have for example C*T*Z then it does not affect the result if we do (C*T)
   *Z or C*(T*Z).

These four properties are all that are needed to call the set E={A,B,C,D,S,T,Y,Z}
with the operation * a Group. This goes into abstract algebra though which
really doesnt have that much to do with programming, although you would be surprised...

Case 2: Not a Square
I don't really know what you are getting at with this but in any respect it is
less interesting programming-wise because it would be for a computer like
trying to rotate the contents of a matrix by 45 degrees. What is that even
supposed to mean for a computer? One thing I would disagree with you on
though is that you claim the angles of rotation to be 45 degrees. If I have
correctly understood what you are doing, then the angular offset will be
different for every height-to-width ratio of the rectangle. Not being 45 degrees
would make any attempt to look for symmetries and all that if nothing else, a
bit harder.

Programming
If I was looking into writing something to detect symmetries in a matrix,
bitmap does't matter what, then I would proceed as follows. As I have
(hopefully) finally cleared up, there are only 8 permutations of the matrix. ie
There are only 8 symmetries to check.

Code:

// Matrix points to an array with data such as Array[Rows][Cols]
int Is_Symetrical(int *Matrix,int Rows,int Cols)
 

{
// Declare variables
int Var=127,i,j; // Note that 127 = 01111111 in binary
 
// Comparing algorithm
for(i=0;i<Rows;i++)
{
for(j=0;j<Cols;j++)
{
if((Var&1 !=0)&&(Matrix[i][j]!=Matrix[j     ][i     ])) Var^=1 ; // S
if((Var&2 !=0)&&(Matrix[i][j]!=Matrix[Rows-i][j     ])) Var^=2 ; // Z
if((Var&4 !=0)&&(Matrix[i][j]!=Matrix[j     ][Cols-i])) Var^=4 ; // D
if((Var&8 !=0)&&(Matrix[i][j]!=Matrix[i     ][Cols-j])) Var^=8 ; // Y
if((Var&16!=0)&&(Matrix[i][j]!=Matrix[Rows-j][i     ])) Var^=16; // B
if((Var&32!=0)&&(Matrix[i][j]!=Matrix[Rows-i][Cols-j])) Var^=32; // C
if((Var&64!=0)&&(Matrix[i][j]!=Matrix[Rows-j][Cols-i])) Var^=64; // T
}
}
 
// Return value representing which symmetries exist (or don't)
return Var;
 
}

There are probably bugs in what I've written since this function has never
seen the light of a compiler or syntax checker, so if you find any fix them up
yourselves and tell me. If anyone does feed this to a compiler though can they tell me?
The details can probably also be tweaked a little (that with Var is a bit wierd but I like it.
Anyone got a better suggestion?) to make it all a bit nicer but hey!

The return value will be 0 if no symmetries exist. If there are symmetries,
then corresponding to each one that exists, the corresponding bit will still be
set. That is, if only the T symmetry exists then the return value will be
64=01000000. If the B symmetry exists as well but is the only other one then
the output will be 80=01010000.

In practice however if T and B are symmetries, then so are T*B=Y and B*T=Z and then
following on from that, all 7 of them (and A the 8th one) are symmetries.
Because of this, only certain return values can come back:

• 0 when there are no symmetries
• 1,2,8,32,64 corresponding to S,Z,Y,C and T respectively
• 52 when B,C and D are symmetries
• 127 when B,C,D,S,T,Y,Z are ALL symmetries

This could probably be used to make a slightly more efficient but more
complicated comparing function, but this one I've made I am convinced runs
so fast that there really isn't a need for that.

And to finish, just because I love maths, I will point out that these specific
return values correspond to the different subgroups of the group which I
described above. For example, one subgroup is {A,B,C,D} under *. Convince
yourself (if you really want to... not likely tho) that {A,B,C,D} satisfies the
four conditions of a group which I mentioned a few paragraphs above.

That would be it for now, and PLEASE DO RESPOND!! Even if just to tell me
that you read this. At least that way I know someone DID read it!! lol!

Philipp

I read and enjoyed your post above, very much, Phillip!

I actually made up a cut out card with holes, and worked with it, but after the one session, I read the next post by the OP, and it was obvious this thread was a transient idea, not to be followed up on by him, in any concrete way.

So I lost interest in the whole thing.

I was so pleasantly surprised to see another post in this thread, but yours was brilliant; a fitting end to a subject (matrix manipulations of all kinds), that is quite intriguing.

Oh well... Only 2h of my life wasted... lol! Not really! I had fun writing that all up, getting it out of my
head where all those ideas were swimming around. Glad you liked my post though! I'm sure that anyone else who comes across this post in the future will also be glad that I summed everything up and gave some answers! Gives this thread a point! Well anyway, we'll probably meet each other on other threads, so till then!

Philipp

Thanks a lot Phillip for your precious time
I got so busy with my work that after my last post in this thread, I stopped thinking about it.

I think it's certain now (after your so much effort) that I will have to perform only 8 compares.

Nice!