group operation: rotation?

[yoshi]

Hej guys,

 

I have a problem which reminds me remotely of a problem I had in my algebra class when it came to group operations. Sadly I can't get it together anymore. Following I try to point out my problem and hope someone could help to get this in a proper mathematic context.

 

Consider a square with 8 node at the edges. Each tuple of two points is connected with a line.

That makes 105 possibilities (7*5*3*1)

(The first node has 7 degrees of freedom, the following node only 5 cause 2 nodes are already connected and so on).

 

But these possibilities are also equal under rotation.

Consider this picture:

The square right hand side is generated by a 90° rotation to the left.

So how can I filter the 105 possibilities for equal states under rotation?

 

As a brute force approach I tried to find some system in the numbers. (I have some nice Java Code if people are interested, showing all 105 possibilities).

 

If necessary it's convenient to identify different states/squares by their connected notes. So the example names are:

17 26 35 48 (left)

13 26 48 57 (right)

 

any help for this is appreciated

 

take care

yoshi

[imatfaal]

Just off the top of my head - and I am clueless about these things: if you count jumps rather than positions I think it might help.

 

no. 1 2 3 4 5 6 7 8

lhs 6 4 2 4 6 4 2 4

rhs 2 4 6 4 2 4 6 4

 

If you just rotate (ie from that sequence of numbers looped over to start again) each number produced to make the smallest or largest - they will be unique, cover every possibility, and wont include extras. Each number would have to add up to 32 so there is a useful checksum.

[DrRocket]

Hej guys,

 

I have a problem which reminds me remotely of a problem I had in my algebra class when it came to group operations. Sadly I can't get it together anymore. Following I try to point out my problem and hope someone could help to get this in a proper mathematic context.

 

Consider a square with 8 node at the edges. Each tuple of two points is connected with a line.

That makes 105 possibilities (7*5*3*1)

(The first node has 7 degrees of freedom, the following node only 5 cause 2 nodes are already connected and so on).

 

But these possibilities are also equal under rotation.

Consider this picture:

The square right hand side is generated by a 90° rotation to the left.

So how can I filter the 105 possibilities for equal states under rotation?

 

As a brute force approach I tried to find some system in the numbers. (I have some nice Java Code if people are interested, showing all 105 possibilities).

 

If necessary it's convenient to identify different states/squares by their connected notes. So the example names are:

17 26 35 48 (left)

13 26 48 57 (right)

 

any help for this is appreciated

 

take care

yoshi

 

 

 

It appears that what you are describing is just the number of ways in which 8 objects can be sorted into (unordered) pairs -- each element in a pair being an end point of one of your lines. This has nothing to do with the geometric arrangement of those points -- as for instance points on the face of a square.

 

For n elements, n even, the number of such pairs [math] \dfrac {n!}{ (\frac{n}{2})!2^{\frac{n}{2}}} [/math].

For the case of n=8, this number is 105.

 

You can find this sort of comcinatorics problem discussed in elementary algebra texts (high school Algebra II) under the heading of "permutations and combinations" (this is a question of combinations).

[yoshi]

@DrRocket:

Nope, what you describe is (was) the first step of the problem. Starting with all permutations on a set of 8 elements (just to be precise: 8!) the task is to reduce identical permutations. Identical means here, that grouping the digits in tuples, each tuple should only appear once no matter of the order.

Example:

78123546 is equivalent to 78354612.

Write this as {78}{12}{35}{46} and {78}{35}{46}{12} this becomes obvious but a pictures is easy done.

 

So the 8! permutations will reduce to 105 configurations. That was the formulae you've posted. In [permutations.txt] you can find the list of these sets.

 

 

Let's say I pick the set: [1, 4, 2, 5, 3, 6, 7, 8]. Assume I print this on a piece of paper and rotate the paper by 90, 180 and 270 degress

And now lets rename the nodes.

16273458 [1, 6, 2, 7, 3, 4, 5, 8]

14273856 [1, 4, 2, 7, 3, 8, 5, 6]

I included the bracket-version so you can easily find them back in the permutations.txt

 

The task is to minimise the 105 configuration so that all missing sets can be produced by rotating the remaining ones.

I hope the explanation is not too long I just want to make sure it's comprehensible.

 

@imatfaal:

Alright, lets see if I get you right ^^

Assuming the left example from my first post 17 26 35 48:

1 maps to 7 => 6 jumps

2 maps to 6 => 4 jumps

3 maps to 5 => 2 jumps

4 maps to 8 => 4 jumps

5 maps to 3 => 6 jumps (5->6->7->8->1->2->3 , yeah we can call this modulo....)

6 maps to 2 => 4 jumps

7 maps to 1 => 2 jumps

8 maps to 4 => 4 jumps

reading the jump column from the top to the bottom we get your posted sequence 64246424

 

Same argumentation maps 13 26 48 57 to 24642464 (right hand side example, previous post).

And yeah for sure all digits will add up to 32.

 

Mapping in a nutshell:

A: 17 26 35 48 -> 64246424

B: 13 26 48 57 -> 24642464

 

We've rotated A once to get B. It seems like we can take the first 2 digits of our "jump sequence" and place these at the end of the number to get the jump sequence of B.

64246424 ->rotate-> 24642464

 

That looks good. While writing this I try out if this works for the for examples posted in this code.

 

Start with A=14253678 and get the jump sequence jump(A)=33355517

 

Successive move the first to digits to the end of the number:

jB = 35551733

jC = 55173335

jD = 17333555

 

Now lets transform these jump sequences back to the usual identifiers.

B* = 14273856

C* = 16273458

D* = 12364758

 

Recall our configurations from above:

12364758, 16273458, 14273856

 

WOW! That looks really good. All jump sequences add up to 32 and to avoid back transformation one could also calculate the jump sequences for B, C and D and compare these to the produced once.

 

-scratch-

I will implement this and will see where I end up with that. A very big thank you for this amazing idea (yeah, I'm stunned ^^).

 

However, I would still like to see a theoretical approach to validate the result. The problem is really interesting me!

permutations.txt

[DrRocket]

@DrRocket:

Nope, what you describe is (was) the first step of the problem. Starting with all permutations on a set of 8 elements (just to be precise: 8!) the task is to reduce identical permutations. Identical means here, that grouping the digits in tuples, each tuple should only appear once no matter of the order.

 

 

 

Which is precisely what I described, and what is given by the expression that I provided.

[yoshi]

Yes, but that's not exactly the problem.

[khaled]

no idea ...

Edited July 26, 2011 by khaled