math question: how to determine unique spatial permutations

Programming Questions

dloghcaz

math question: how to determine unique spatial permutations

in Programming Questions • 2 years ago

I have a bit of a math question for a Sol Lewitt sort of project. Say I have a 4x4 grid with 16 possible positions and 4 points that can each fill one of those positions at a time. I want to systematically determine all of the unique permutations of the positioning of the 4 points. I think I could probably work this out with some for loops, but I'm not sure how to screen for translation and rotation. I think it's best if I explain this visually:

xooo ooox

oxoo ooxo

ooxo oxoo
ooox should not be unique from xooo as it represents the same shape translated around the center axis. Similarly,

xxoo ooxx

oooo oooo

oooo should not be unique from oooo as it was simply translated two positions to the right.

Additionally, I would be interested in any reading on these types of problems that only requires elementary math.

Thanks!

Zach

Replies(3)

tfguy44

Re: math question: how to determine unique spatial permutations

2 years ago

What about reflections?

That is, would:

xooo

oooo

xxxo

Be the same (not unique from) as:

ooox

oooo

oxxx

dloghcaz

Re: math question: how to determine unique spatial permutations

2 years ago

Yes, I'd like to filter them out as well. Thanks for point that out. I think I forgot about reflection because many cases are also covered by rotation if there's sufficient symmetry.

kooogy

Re: math question: how to determine unique spatial permutations

2 years ago

there are 16*15*14*13 possibles, 43680 which shouldn't take too long

i'd iterate through them adding the figure and every transformation of it to a hashmap. if the new possibility isn't already in the hashmap then add it to the list of unique shapes.

combinations would include(?)
4 rotations
4 shifts horizontally
4 shifts vertically
4 reflections

you'll need to think of a way of describing the possibilities (a short would suffice, 16 bits) and the transformation code (an array of indices denoting the mapping).

Top Reply