On Dec 2, 4:07*pm, "BartC" <b...@freeuk.com> wrote:
> "lloyd" <lloyd.hough...@gmail.com> wrote in message
>
> news:89b6e614-0a63-4dca-84ce-...
>
> > So I have a little program that enumerates rectangular arrays of small
> > integers with a particular property. Each rotation and reflection of a
> > solution is valid, but when you rotate/reflect, the entries in each
> > cell of the array are transformed too. I want to enumerate the reduced
> > count of solutions that have been rotated and reflected into a canonic
> > form, but I also want to enumerate the larger number of solutions that
> > include all rotations and reflections as separate. My generating
> > program will reach all possibilities eventually.
>
> Difficult to see exactly what you are trying to achieve. So you have a
> rectangular array of small integers, for example:
>
> 10 20 30
> 40 50 60
>
> And with mirroring and flipping you have 3 more:
>
> 30 20 10
> 60 50 40
>
> 40 50 60
> 30 20 10
>
> 60 50 40
> 30 20 10
>
> And with 90-degree rotation of the original, you have this:
>
> 40 10
> 50 20
> 60 30
>
> And by mirroring and flipping of that you have 3 more, total 8 arrangements
> (the same number of ways you could put a 5.25" floppy into a drive, of which
> only one was correct...)
>
> (And I understand that if the array is not square, you don't bother with
> rotations, as presumably they can't be solutions.)
>
> So assuming the above is correct, you have these 4 or 8 matrices, what are
> you trying to achieve again?
Hi Bart, say this is a valid array (I won't bother explaining what my
problem means by "valid"):
3 6 1
5 4 9
Then automatically the reflections and rotations of this array are
also valid. They are:
1 6 3
9 4 5
5 4 9
3 6 1
9 4 5
1 6 3
My program, as it performs a back-tracking search for these and other
similar valid solutions, will encounter each of these as it goes, and
first verify that the array is valid. Then it calls best_symmetry() to
determine whether the valid array it has encountered is in canonical
form or not. For my purposes I use the lexicographically "lowest",
when the array is read by rows and flattened. So as my program goes
through all potential solutions, it examines the four above when it
validates them, and inquires of best_symmetry() whether or not the
array is in canonical form. It receives an answer of "no" for the 1st,
3rd and 4th arrays above, and "yes" for the 2nd array above. The code
I submitted was my attempt at an efficient check of canonicity. I bail
out as soon as I notice that another array would be lower, which in
this case would happen when I checked the top right-hand corner of the
horizontal reflection.
If the array had been square, I would need to perform another four
transformations to see whether I had the best form.
An additional complication that I needn't have mentioned, but did in
my first version, is that every integer entry, in an array when it is
reflected or rotated, is itself transformed. The array T[][] holds
these transformations, and it looks like this:
const int T[8][9] = {{0, 1,2,3,4, 5,6, 7,8},
{0, 4,3,2,1, 5,6, 8,7},
{0, 2,1,4,3, 5,6, 8,7},
{0, 3,4,1,2, 5,6, 7,8},
{0, 1,4,3,2, 6,5, 7,8},
{0, 2,3,4,1, 6,5, 8,7},
{0, 4,1,2,3, 6,5, 8,7},
{0, 3,2,1,4, 6,5, 7,8}};
That's why I need to send array entries through the T[][] transform
while I am testing each transformation.
Thanks,
Lloyd
Similar Threads
