<p>I'm searching for an algorithm to do the following:</p>

<pre><code>A 1-&gt;3
B 2-&gt;6
C 4-&gt;5
D 5-&gt;2
E 6-&gt;4
F 3-&gt;7
G 8-&gt;9
H 10-&gt;11
</code></pre>

<p>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?</p>

<p>possible solution:</p>

<pre><code>G 8-&gt;9   in step 1
F 3-&gt;7   in step 1
E 6-&gt;11  in step 1
A 1-&gt;3   in step 2
B 2-&gt;6   in step 2
C 4-&gt;5   in step 3
E 11-&gt;4  in step 4
D 5-&gt;2   in step 4
E 1-&gt;4   in step 5
H 10-&gt;11 in step 5
</code></pre>

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

<h1>Edit</h1>

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

<p><strong>the longest cycle + the shortest chain + 1</strong></p>

<p>or</p>

<p><strong>the longest chain (if that is longer then the one above)</strong></p>

<p>right?</p>

<p>not:</p>

<p>suppose we have the first case:</p>

<p>long cycle + short chain</p>

<p>in step 1 we break the cycle by moving element <strong>Z</strong> start fixing other chains</p>

<p>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 <strong>Z</strong> to.
with element <strong>Z</strong> out of the way we can fix the shortest chain before the longest cycle is finished:</p>

<p>making the least possible steps:</p>

<p><strong>the longest cycle + 1</strong></p>

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

<p><strong>1 + one cycle + last cycle</strong></p>

<p>any ideas of an approach to this problem?</p>

CC BY-SA 3.0
2011-10-10T20:00:52.053Z
so you need at most one extra unit of space then (for the cycles). @JukkaSuomela convert to answer ?
Suresh Venkat
CC BY-SA 3.0
2011-10-13T16:49:44.237Z
Right, I overlooked the fact that you are looking for a *parallel* algorithm here. I'll add a tag to emphasise it.
Jukka Suomela
CC BY-SA 3.0
2011-10-13T16:56:52.950Z
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
CC BY-SA 3.0
2011-10-14T11:22:44.303Z
yes, as many moves as you want in parallel.
Berty
<ds.algorithms><graph-algorithms><dc.parallel-comp><sorting-network>
Algorithm for permuting elements using constant work space
Berty
# Algorithm for permuting elements using constant work space

(Asked by: username_0 on 2011-10-10)

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?

**Tags:** ds.algorithms, graph-algorithms, dc.parallel-comp, sorting-network

> **Comments:**
> **username_1**: so you need at most one extra unit of space then (for the cycles). @JukkaSuomela convert to answer ?  
> **username_2**: Right, I overlooked the fact that you are looking for a *parallel* algorithm here. I'll add a tag to emphasise it.  
> **username_2**: 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?  
> **username_0**: yes, as many moves as you want in parallel.  

---

## 0 answers

