4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A similar task can be found on SO, that should probably help. A simple way to look at it is to take the Hamming distance, which you can get in O(n). If you don't actually have to run the swap, but only calculate the number of swaps required, then that only depends on whether 0 is initially at the correct position. Take care not to get this mixed up with the Kendall-tau-distance, which only allows for swapping adjacent entries. $\endgroup$ – G. Bach Aug 26 '13 at 19:44
9
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ in the above example(given by you) we can use variant of selection sort on source array{0,3,2,1} to get target {0,1,2,3}. But is that minimum number of swaps? $\endgroup$ – akshay Aug 26 '13 at 12:38
  • $\begingroup$ After relabeling source and target, for each i=0 to n-1, swap 'i' with new swap element(in example its 3) if its not already in the final position. $\endgroup$ – akshay Aug 27 '13 at 6:38
  • $\begingroup$ The directed graph you mentioned is permutation cycles.Can you please elaborate,how and why in second diagram node 0 points to 5 and node 6 points to 0? $\endgroup$ – akshay Aug 28 '13 at 17:12
  • $\begingroup$ @akshay: it's only an example: 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 interpret the swaps on a cycle like a shift of its numbers. $\endgroup$ – Vor Aug 28 '13 at 17:26
  • $\begingroup$ Got it. In the example use of 0 as swap element is for illustration purpose right?In general we need to swap with some element x? $\endgroup$ – akshay Aug 28 '13 at 17:43
-1
$\begingroup$

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}

$\endgroup$
  • 3
    $\begingroup$ This isn't enough to solve the problem. Hint: Try modeling what happens when you start with {1,0,3,2} and want to reach {0,1,2,3}. You will first swap 1 and 0, reaching {0,1,3,2}, and then your process will stop, since 0 is in its correct place. However, you haven't reached the desired ending point yet. So your algorithm needs some work.... $\endgroup$ – D.W. Aug 26 '13 at 18:21
  • $\begingroup$ In the example I wrote, the program reached the state you mention with {4,1,0,3,2} where the 0 is in its correct place but we haven't reached the desired ending point. There you just have to swap the 0 with any number (e.g. the first one) which is not on the desired position. In your example, after reaching state {0,1,3,2} you just swap 0 with either 3 or 2 and the process can continue. $\endgroup$ – Arzaquel Aug 26 '13 at 19:16
  • 2
    $\begingroup$ OK. Now you have two more questions you'll need to address, to demonstrate that this is a correct solution: (1) How do you know this is sufficient (that this procedure will always terminate in a finite set of steps)? (2) How do you know that your procedure will result in the minimum possible number of swaps? (i.e., that there is no other way to do it with fewer swaps?) I think you have something substantial to prove here; until you've proven that, it's not clear that this is a valid solution. $\endgroup$ – D.W. Aug 26 '13 at 23:23
-1
$\begingroup$

@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;
}
$\endgroup$
  • $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – D.W. Aug 9 '16 at 6:53
-2
$\begingroup$

@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);
}
$\endgroup$
  • 2
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – D.W. Aug 9 '16 at 6:53
  • $\begingroup$ @TomvanderZanden, I'm not seeing how this is an exact copy of ThinkRecursively's answer. The first line looks similar, but the code looks different to me. Or is there some similarity I'm overlooking? $\endgroup$ – D.W. Aug 9 '16 at 7:49
  • $\begingroup$ Uh, I just saw two source code answers and they both started with "@Vor's solution is awesome!" so I thought they were a copy of each other. My bad. $\endgroup$ – Tom van der Zanden Aug 9 '16 at 7:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.