I'm searching for an algorithm to do the following:

A 1->3
B 2->6
C 4->5
D 5->2
E 6->4
F 3->7
G 8->9
H 10->11

Elements A-H are stored on locations 1 to 11 (some locations are vacant). We need to move the elements from their original position to the new position. What order requires the least amount of steps?

possible solution:

G 8->9   in step 1
F 3->7   in step 1
E 6->11  in step 1
A 1->3   in step 2
B 2->6   in step 2
C 4->5   in step 3
E 11->4  in step 4
D 5->2   in step 4
E 1->4   in step 5
H 10->11 in step 5

Notice that E is moved twice because of a loop: C->D->B->E->C


this is more complex then it seams: the longest time that you'll need is:

the longest cycle + the shortest chain + 1


the longest chain (if that is longer then the one above)



suppose we have the first case:

long cycle + short chain

in step 1 we break the cycle by moving element Z start fixing other chains

in step x we have finished some of the shorter chains. meaning: we have some extra free places. so we can use those to move element Z to. with element Z out of the way we can fix the shortest chain before the longest cycle is finished:

making the least possible steps:

the longest cycle + 1

but if we only have cycles and they are equally long then the minimal number of steps becomes:

1 + one cycle + last cycle

any ideas of an approach to this problem?

  • 3
    $\begingroup$ so you need at most one extra unit of space then (for the cycles). @JukkaSuomela convert to answer ? $\endgroup$ – Suresh Venkat Oct 10 '11 at 20:00
  • $\begingroup$ Right, I overlooked the fact that you are looking for a parallel algorithm here. I'll add a tag to emphasise it. $\endgroup$ – Jukka Suomela Oct 13 '11 at 16:49
  • $\begingroup$ So what are the rules of the game precisely? We can move $a \to b$ and $c \to d$ in parallel if both $b$ and $d$ are empty before this step? $\endgroup$ – Jukka Suomela Oct 13 '11 at 16:56
  • $\begingroup$ yes, as many moves as you want in parallel. $\endgroup$ – Berty Oct 14 '11 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.