Thanks Raul and John for being so kind to react om my e-mail.
What follows is: because I want to know!
John Randall wrote:
>
> The generating moves are even permutations, e.g.
>
> C. 3 2 1 0 4 5
> +---+---+-+-+
> |2 1|3 0|4|5|
> +---+---+-+-+
>
> so any odd permutation of the solution is unsolvable (like the trick
> version of the 15 puzzle). I think it is probably the full alternating
> group, although I am not completely sure.
>
What I learned so far from group theory is:
The size (order) of the group of permutations in this case is
!6
720
The size of the alternating group is
-: !6
360
and that's equal to
# P
360
in Roger Hui's solution and,
from Raul's remarks
p=: o (] ~.@, ,/@:({"1/))^:_,:n
# p
360
I compared P with the set of even permutations A6 (the alternating group).
I used the following:
parity =: -: /:@/: * _1:^>/~ ~:/@,@:* </[EMAIL PROTECTED]@# NB. from
JPhrases/ParitySymmetry
check parity of all elements of P:
+/ 1 = parity "1 P
360
or perhaps
(360#1) -: parity "1 P
1
perm=: [EMAIL PROTECTED] A. i. NB. of course, I copied that too from
Essays/Permutations
b =: parity "1 perm 6
A6 =: b#perms NB. set of even permutations
Do they match?
A6 -: /:~ P NB. have to sort P
1
also
A6 -: /:~ <: p
1
Voila !
I hope I didn't get lost somewhere, but in this way the conclusion is
that the alternating set (A6) of P6 is equal to the sets in your J-programs.
> Since, as Raul suggests, you can generate the complete set of solutions
> and so decide the shortest solution. Using group theory alone, you need
> to apply techniques used in word problem questions. I guess this would be
> useful if the "cube" were bigger.
>
>
You're right. The size of the problem is small enough for this kind
of approach. (without not being impressed though by.the solutions given
by you guys).
Raul Miller wrote:
>
> Given the desired end position
> n=:1 2 3 4 5 6
>
> and the three valid moves (represented as indices in the new
> positions for each of the values at their previous positions)
> o=: 3 2 1 0 4 5,0 4 3 2 1 5,:0 1 5 4 3 2
>
> You can generate a list of all possible moves connected to the
> end position by those moves
> p=: o (] ~.@, ,/@:({"1/))^:_,:n
>
food for me ;-)
> Any permutations not in p are unsolvable as each of the valid
> moves are self inverting:
> o{"1 o{"1 n
>
For my understanding this means the product of f*f = identity
Have to work on that one too...
Thanks for your patience, so far an instructive experience for me.
&
greetings from The Netherlands.
@@i <=> Arie
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
