Rearrange an array using swap with 0

Problem Detail: 

This is a Google interview question. I got it from a website.

You have two arrays source and target, containing two permutations of the numbers [0..n-1]. You would like to rearrange source so that it equals to target. The only allowed operations is "swap a number with 0". Find the minimum number of swaps?

e.g. {1,0,2,3} -> {1,3,2,0} swap 0 with 3. one swap is enough.

My attempt on problem: If we consider arrays as strings we could use edit distance to convert source to target if other edit distance operations like insert,delete,replace etc are allowed but here only allowed operation is swapping.

Asked By : akshay

Answered By : Vor

Without loss of generality you can assume that the target array is $0,1,...,n-1$: you can "relabel" the target array as 0,1,2,...,n-1 (and relabel the corresponding numbers in the source array, too). The allowed operation becomes "swap a number with x" (where x is not necessarily 0) and the target array is 0,1,2,...,n-1.

You can build a directed graph with $n$ nodes and an edge from node $n_i$ to node $n_j$ if $n_i = j$, i.e. the target position of $n_i$ is $j$ (skip nodes that are already in the correct position). The resulting graph contains one or more distinct cycles.

You can arrange the cycle containing the zero following the arcs in the reverse direction, then "jump" to another cycle and arrange it; the "entry point" doesn't matter.

In the example of the figure above the swap number is zero and the target permutation is $0,1,...6$; after completing the first cycle (blue one) you must enter the second cycle (red one) in order to complete it; if $(n_i \rightarrow n_j)$ is a directed arc of the second cycle, then it must modified in $(n_i \rightarrow 0 \rightarrow n_j)$. The "entry point" is irrelevant (the number of swaps needed to arrange the second cycle doesn't change). You can also interpret the swaps on a cycle like a shift of its numbers.

The procedure always ends with the sorted array (after arranging a cycle, its numbers are never moved again). If there are $m$ cycles and the $i$-th cycle has $p_i>1$ numbers that needs to be arranged and cycle 1 contains the number used for the swaps, the total number of swaps is $(p_1-1)+(p_2+1)+...+(p_m+1)$. If the number used for the swaps is already in place the number of swaps is $(p_1+1)+(p_2+1)+...+(p_m+1)$. To prove that the number of swaps used is optimal, you can observe that every number of each cycle must be moved (requires a swap), and there is no way to move a number of a cycle without "moving" the zero on that cycle.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13930