--- artist google <[EMAIL PROTECTED]> wrote:
> I think this is sort of equivalent to the rubic cube.
> where u can scramble the cube within a second, but
> then try forever to get the solution (unless ofcourse
> if you know the tricks).
--- Abigail <[EMAIL PROTECTED]> wrote:
> Consider the sequence: [A B C D E], for some number A,
> B, C, D and E. There are just three operations possible,
> giving the sequences [E D C B A], [D C B A E] and
> [A E D B C]. Note that none of the operations changes the
> parity of the sequence. Note that [2 1 3 4 5] has an odd
> parity, while the parity of [1 2 3 4 5] is even. But if no
> operation can change the parity, there's no way of going
> from [2 1 3 4 5] to [1 2 3 4 5].
This situation is very similar to the rubix cube idea, where
if you dismantle your rubix cube and reassumble it jumbled
up then it's highly possible that it cannot be completed.
(Even if you know how, as I do).
--- artist google <[EMAIL PROTECTED]> wrote:
> I am not looking for randomly achieved solutions.
> and looking for minimum steps to achieve solution.
> I thought that was obvious.
The *Only* approach to the best solution I can think of is
a Breadth First Search. This should always find the best
solution, at the cost of many, many CPU cycles. Obviously
two optimisations should be applied:
* Create MD5 (or similar) hash values for each list we
check, because as the operations are applied we are
likely to find lists identical to that already found.
* To conserve memory, we should only store a complete
list every X levels deep. Between these levels we
store a "diff"... I.e. the set of operations required.
For partially sorted lists, this would return fairly quickly
and with the correct solution. However, I think it probably
shares a property with the traveling salesman problem:
* The best solution takes a LONG time to find, but a nearly
optimal solution may take far less time.
Anyone for an implementation or further comment?
Jonathan Paton
=====
s''! v+v+v+v+ J r e P h+h+h+h+ !s`\x21`~`g,s`^ . | ~.*``mg,$v=q.
P ! v-v-v-v- u l r e r h-h-h- !12.,@.=m`.`g;do{$.=$2.$1,$.=~s`h
E ! v+v+v+ s k e h+h+ !`2`x,$.=~s`v`31`,print$.[$v+=$.]
R ! v-v- t H a c h h- !}while/([hv])([+-])/g;print"\xA"
L ! A n o t !';$..=$1while/([^!]*)$/mg;eval$.
__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
