Easily rearranging arguments without using FA
See also: rearranging arguments without using FA
September 16 2015
Zearen | It's common knowledge that the cluster se te se swaps the second and third position. How do you construct a minimal SE cluster to create an arbitrary place structure. |
selpahi | I think any method is still too difficult to work for real-time human processing |
durka42 | ... permutation groups |
Zearen | durka42: I tried that, but a lot of it's built on orbits and transpositions of the form (k (k+1)) Our building blocks are different. We use orbits of the form (1 k) I've shown three identities which are really all you need: Let SE be the set of SE. We consider strings of SE and call this set "SE*". Let Ø be the empty string. ∀ a ∈ SE : aa = Ø We can observe that each SE is a function and a permutation, and that a string can be interpreted as a composition in the normal order. I will now show that for r_k ∈ SE, r_1 r_2 ... r_k r_1 = r_2 ... r_k r_1 r_2 i ≠ j <=> r_i ≠ r_j We call this operation a rotation. As a concrete example se te ve se broda = te ve se te broda. You can verify yourself, if you wish Proof-ish thing: The basic idea is that we're using the 1st position as a sort of swap space to build an orbit. Whenever we do the first swap we store the first position that spot then we store each successive position in the spot that follows. Finally, we restore the 1 position and swap the final value from the chain into the starting position, completing the orbit. Let's say we want the place structure 1 4 2 3 5. That is 4 -> 2 2 -> 3 and 3 -> 4 In a permutation group, we call such a permutation an "orbit" We would write it this way: (4 2 3) or equivalently (2 3 4) We reverse it, and translate it into conversions: «ve te se», then tack on a «se» or a «ve» to restore the position to get se ve te se or ve te se ve. |
selpahi | I'm assuming we'll be using a buffer position to break into new "orbits"? |
Zearen | Correct. The reason we reverse is because the order of application is reversed for orbits and SE. |
selpahi | What about (3 4 2) ? |
Zearen | Also equivalent. It's the fact that we can rotate orbits like that that we use to prove (2) :) That would be «te se ve te», of course. |
selpahi | This seems exactly the same as rubik's cube BLD cycles, except having to go backwards because of SE. |
Zearen | So we start with: 1 2 3 4 5 2 1 3 4 5 (se) 3 1 2 4 5 (te) 4 1 2 3 5 (ve) 1 4 2 3 5 (se) This technique allows us to arbitrarily re-arrange the last 4 places. |
selpahi | Well this is way easier than doing each step in one's mind. Only problem is that backwards SE is confusing |
Zearen | It still takes a bit of mental gymnastics. At a certain point, just use FA or some ce'u binding thing. We still need to be able to swap into x1. This is easy though: There are two cases. (3.1) The x1 conversion is a place not being re-arranged in the last four We call a sequence "1-preserving" if c1 = x1 after the conversion is complete. We note that for 1-preserving sequences r_1 ... r_n, r_i ∈ SE we can tack a q ∈ SE on either side for free. Further, all conversions of the form in (2) are 1-preserving. We already showed this. So that case is easy. (3.2) The c1 is part of the cycle. This means that there is a position r = x1 by defintion. If we tack two conversions for position r onto a side of the conversion, we get an identical conversion (1) with a 1-preserving sub-conversion. We can then rotate the sub-conversion via (2) We then apply (1) again to eliminate it. Let's consider: 2 4 1 3 5 First we change it into a one preserving conversion: 1 4 2 3 5 (te C where C ∈ SE*) We know how to solve this kind. It's the orbit (4 2 3). Therefore C = ve te se ve So our conversion is: te ve te se ve But wait, we can reduce this. Let's rotate te (ve te se ve) te te se ve te se ve te (1) Now let's see if it works ^^ 1 2 3 4 5 3 2 1 4 5 (te) 4 2 1 3 5 (ve) 2 4 1 3 5 (se) It works ! |
selpahi | Rotations work on any length of SE right? |
Zearen | I think this is more of a for-fun thing. I'm not sure it's practical. |
selpahi | It's not practical, in that using multiple SE in a row is ugly and rare, but it's more practical than memorizing all the SE* combinations and their resulting place structures |
Zearen | Kind of. They have to be of form r_1 ... r_n r_1 and ∀ 1 ≤ i, j ≤ n; i ≠ j <=> r_i ≠ r_j I.e. you can't rotate te se ve nor se te ve te se. |
selpahi | Can I rotate te se te or se te se? What would be a five-tuple that I can rotate? |
Zearen | se te ve te se -> se te ve se se te se -> (te ve se te) se te se -> te ve se te (te se te) -> te ve se te te se te -> te ve se se te -> te ve te I see an easier way to compute it. se is its own inverse and te ve te is 1-preserving :) But it's fun to do the arithmetic, too. Yeah, it's not clear. te se te can be rotated to se te se can be rotated to te se te etc. Actually, te se te = se te se is a fun corollary. More generally, a,b ∈ SE; a b a = b a b. Case a = b is trivial (a a a = a a a = a). Case a ≠ b is a rotation. |