algorithm hint needed. please.

This is a discussion on algorithm hint needed. please. within the C Programming forums, part of the General Programming Boards category; Note that "Not Mirrored" is the same position as "Rotated 0 degrees", so 16 is highly suspect....

  1. #16
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Note that "Not Mirrored" is the same position as "Rotated 0 degrees", so 16 is highly suspect.

  2. #17
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  4. #19
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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!

  5. #20
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    But isn't flip and mirror the same thing?

    If you think of it as the transparent sheet with a grid, then you can rotate it a number of ways. 4 x 90 degree rotations.
    Each of those four can then be flipped in three directions [you can flip the sheet so that it's upside down or so that it's left-becomes-right, or holds the corners and flip [diagonally]]. So that's three different flips, plus the "unflipped". That makes 4 different ways.

    4 * 4 = 16 ways.

    I don't think you can come up with any more, or any less.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #21
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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 ...

  7. #22
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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).

  8. #23
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Right, we have four positions of rotation: Let's call them A, B, C and D. [One of these are of ocruse "unrotated"]
    We then have 4 flipping variants, let's call them X, Y, Z, W [the first one is of course "unflipped"]

    We then get the following combinations:
    AX
    AY
    AZ
    AW
    BX
    BY
    BZ
    BW
    CX
    CY
    CZ
    CW
    DX
    DY
    DZ
    DW

    Of course AX is an unchanged image, and BX for example is not flipped, but rotated. AY on the other hand is unrotated but flipped.

    Am I missing something here?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #24
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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...

  10. #25
    Registered User starcatcher's Avatar
    Join Date
    Feb 2008
    Location
    Australia
    Posts
    45

    Lightbulb Finally the answer...

    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

  11. #26
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  12. #27
    Registered User starcatcher's Avatar
    Join Date
    Feb 2008
    Location
    Australia
    Posts
    45
    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

  13. #28
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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!

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithm needed!
    By Warlax in forum C++ Programming
    Replies: 6
    Last Post: 05-11-2006, 01:42 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Algorithm needed
    By sean in forum C++ Programming
    Replies: 17
    Last Post: 08-22-2002, 08:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21