Algorithm for permuting elements using constant work space

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

Edit

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

the longest cycle + the shortest chain + 1

or

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

right?

not:

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?

• so you need at most one extra unit of space then (for the cycles). @JukkaSuomela convert to answer ? – Suresh Venkat Oct 10 '11 at 20:00
• Right, I overlooked the fact that you are looking for a parallel algorithm here. I'll add a tag to emphasise it. – Jukka Suomela Oct 13 '11 at 16:49
• 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? – Jukka Suomela Oct 13 '11 at 16:56
• yes, as many moves as you want in parallel. – Berty Oct 14 '11 at 11:22