Rearrange an array using swap with 0

Question

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.

Answer 1

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.

Answer 2

In order to minimize the number of swaps, each time the 0 is not in its correct place you can take advantage of its current position and swap it with the number that should go there.

For example, if you have {3,1,4,0,2} and you want {4,2,0,3,1} the 0 is not in its correct position, and the number that should go there is 3 so you swap them, on the next iteration you have {0,1,4,3,2}. Again the 0 is not on its correct position so you swap it with 4 to obtain {4,1,0,3,2}. This time the 0 is on the correct position so you just swap it with the any number which is not yet on the desired position, say 1 {4,0,1,3,2} and continue with the original process {4,2,1,3,0} and finally {4,2,0,3,1}

Answer 3

@Vor's solution is awesome! Here is a Java implementation for that:

// 0 1 2 3
// 3 2 1 0  (0,3) (1,2)
// http://cs.stackexchange.com/questions/13930/rearrange-an-array-using-swap-with-0
public static int sortWithSwap(int [] a) {
    Integer[] A = new Integer[a.length];
    for(int i=0; i<a.length; i++)   A[i] = a[i];
    Integer[] B = Arrays.copyOf(mapping(A), A.length, Integer[].class);

    HashSet<Integer> all = new HashSet<>();
    List<HashSet<Integer>> list = new ArrayList<>();
    list.add(new HashSet<Integer>());

    for(int i=0; i<B.length; ) {
        HashSet<Integer> cur = list.get(list.size()-1);
        if(!all.contains(B[i])) {   // add to existing cycle
            all.add(B[i]);
            cur.add(B[i]);
            i = B[i];
        } else {
            if(cur.contains(B[i])) {     // duplicate in existing cycles
                list.add(new HashSet<Integer>());
            }
            i++;
        }
    }

    list.remove(list.size() - 1);     // remove last empty set
    int sum = 0;
    for(int i=0; i<list.size(); i++) {
        HashSet<Integer> cur = list.get(i);
        if(cur.size() <= 1) continue;
        if(cur.contains(0)) {
            sum += cur.size() - 1;
        } else {
            sum += cur.size() + 1;
        }
    }

    return sum;
}

// a b b c
// c a b b
// 3 0 1 1
private static Object[] mapping(Object[] A) {
    Object[] B = new Object[A.length];
    Object[] ret = new Object[A.length];
    System.arraycopy(A, 0, B, 0, A.length);
    Arrays.sort(A);
    HashMap<Object, Integer> map = new HashMap<>();
    for(int i=0; i<A.length; i++) {
        map.put(A[i], i);
    }

    for(int i=0; i<B.length; i++) {
        ret[i] = map.get(B[i]);
    }
    return ret;
}

Answer 4

@Vor's solution is awesome!My simple solution.

public static void ReArray(int[] src) {

    if (src == null || src.length == 0) {
        return;
    }

    int[] reverseSrc = new int[src.length];

    for (int i = 0; i < src.length; i++) {
        reverseSrc[src[i]] = i;
    }

    for (int i = 0; i < src.length; i++) {
        if (reverseSrc[i] == i) {
            continue;
        }

        if (reverseSrc[0] == 0) {
            swap(reverseSrc, 0, i);
            System.out.println(Arrays.toString(reverseSrc));
        }

        while (reverseSrc[0] != 0) {
            swap(reverseSrc, 0, reverseSrc[0]);
            System.out.println(Arrays.toString(reverseSrc));
        }
    }

    System.out.println(Arrays.toString(reverseSrc));
}

public static void swap(int[] reverseSrc, int a, int b) {
    int temp = reverseSrc[a];
    reverseSrc[a] = reverseSrc[b];
    reverseSrc[b] = temp;
    System.out.format("Positon %d and Position %d are swaped. \n", a, b);
}