Compute the minimal number of swaps to order a sequence

Question

I'm working on sorting an integer sequence with no identical numbers (without loss of generality, let's assume the sequence is a permutation of 1,2,...,n) into its natural increasing order (i.e. 1,2,...,n). I was thinking about directly swapping the elements (regardless of the positions of elements; in other words, a swap is valid for any two elements) with minimal number of swaps (the following may be a feasible solution):

Swap two elements with the constraint that either one or both of them should be swapped into the correct position(s). Until every element is put in its correct position.

But I don't know how to mathematically prove if the above solution is optimal. Anyone can help?

Solution 1

I was able to prove this with graph-theory. Might want to add that tag in :)

Create a graph with n vertices. Create an edge from node n_i to n_j if the element in position i should be in position j in the correct ordering. You will now have a graph consisting of several non-intersecting cycles. I argue that the minimum number of swaps needed to order the graph correctly is

M = sum (c in cycles) size(c) - 1

Take a second to convince yourself of that...if two items are in a cycle, one swap can just take care of them. If three items are in a cycle, you can swap a pair to put one in the right spot, and a two-cycle remains, etc. If n items are in a cycle, you need n-1 swaps. (This is always true even if you don't swap with immediate neighbors.)

Given that, you may now be able to see why your algorithm is optimal. If you do a swap and at least one item is in the right position, then it will always reduce the value of M by 1. For any cycle of length n, consider swapping an element into the correct spot, occupied by its neighbor. You now have a correctly ordered element, and a cycle of length n-1.

Since M is the minimum number of swaps, and your algorithm always reduces M by 1 for each swap, it must be optimal.

Solution 2

All the cycle counting is very difficult to keep in your head. There is a way that is much simpler to memorize.

First, let's go through a sample case manually.

• Sequence: [7, 1, 3, 2, 4, 5, 6]
• Enumerate it: [(0, 7), (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (6, 6)]
• Sort the enumeration by value: [(1, 1), (3, 2), (2, 3), (4, 4), (5, 5), (6, 6), (0, 7)]
• Start from the beginning. While the index is different from the enumerated index keep on swapping the elements defined by index and enumerated index. Remember: swap(0,2);swap(0,3) is the same as swap(2,3);swap(0,2)
  • swap(0, 1) => [(3, 2), (1, 1), (2, 3), (4, 4), (5, 5), (6, 6), (0, 7)]
  • swap(0, 3) => [(4, 4), (1, 1), (2, 3), (3, 2), (5, 5), (6, 6), (0, 7)]
  • swap(0, 4) => [(5, 5), (1, 1), (2, 3), (3, 2), (4, 4), (6, 6), (0, 7)]
  • swap(0, 5) => [(6, 6), (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (0, 7)]
  • swap(0, 6) => [(0, 7), (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (6, 6)]

I.e. semantically you sort the elements and then figure out how to put them to the initial state via swapping through the leftmost item that is out of place.

Python algorithm is as simple as this:

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]


def minimum_swaps(arr):
    annotated = [*enumerate(arr)]
    annotated.sort(key = lambda it: it[1])

    count = 0

    i = 0
    while i < len(arr):
        if annotated[i][0] == i:
            i += 1
            continue
        swap(annotated, i, annotated[i][0])
        count += 1

    return count

Thus, you don't need to memorize visited nodes or compute some cycle length.

Solution 3

For your reference, here is an algorithm that I wrote, to generate the minimum number of swaps needed to sort the array. It finds the cycles as described by @Andrew Mao.

/**
 * Finds the minimum number of swaps to sort given array in increasing order.
 * @param ar array of <strong>non-negative distinct</strong> integers. 
 *           input array will be overwritten during the call!
 * @return min no of swaps
 */
public int findMinSwapsToSort(int[] ar) {
    int n = ar.length;
    Map<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < n; i++) {
        m.put(ar[i], i);
    }
    Arrays.sort(ar);
    for (int i = 0; i < n; i++) {
        ar[i] = m.get(ar[i]);
    }
    m = null;
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int val = ar[i];
        if (val < 0) continue;
        while (val != i) {
            int new_val = ar[val];
            ar[val] = -1;
            val = new_val;
            swaps++;
        }
        ar[i] = -1;
    }
    return swaps;
}

Solution 4

We do not need to swap the actual elements, just find how many elements are not in the right index (Cycle). The min swaps will be Cycle - 1; Here is the code...

static int minimumSwaps(int[] arr) {
        int swap=0;
        boolean visited[]=new boolean[arr.length];

        for(int i=0;i<arr.length;i++){
            int j=i,cycle=0;

            while(!visited[j]){
                visited[j]=true;
                j=arr[j]-1;
                cycle++;
            }

            if(cycle!=0)
                swap+=cycle-1;
        }
        return swap;


    }

Solution 5

@Archibald, I like your solution, and such was my initial assumptions that sorting the array would be the simplest solution, but I don't see the need to go through the effort of the reverse-traverse as I've dubbed it, ie enumerating then sorting the array and then computing the swaps for the enums.

I find it simpler to subtract 1 from each element in the array and then to compute the swaps required to sort that list

here is my tweak/solution:

def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

def minimum_swaps(arr):

    a = [x - 1 for x in arr]

    swaps = 0
    i = 0
    while i < len(a):
        if a[i] == i:
            i += 1
            continue
        swap(a, i, a[i])
        swaps += 1

    return swaps

As for proving optimality, I think @arax has a good point.

View more solutions

Comments

[Bernhard Barker]

Highly related / duplicate: Minimum number of swaps needed to change Array 1 to Array 2?

[puneet]

what will be time complexity of this?

[Rewanth Tammana]

Time complexity : O(n*logn) Space complexity : O(n) @puneet

[GURMEET SINGH]

Can you explain what is happening in last while loop

[AnT stands with Russia]

But how is that a proof of minimality? "I argue that the minimum number of swaps...", "Take a second to convince yourself of that..." Sorry, "arguing" and "convincing yourself" is not enough. You have to actually prove that the above M is minimal.

[Spindoctor]

Can anyone help with understanding the code? I can't seem to grasp the logic behind what is happening

[Spindoctor]

@GURMEETSINGH did you figure out the algorithm?

[GURMEET SINGH]

@Spindoctor yes I figured it out

[Spindoctor]

@GURMEETSINGH, can you please share your understanding of the logic? I can't understand it.

[GURMEET SINGH]

@Spindoctor in first for loop it is keeping the actual value as key and the position in the original array as value. Then the array is sorted using Collections.sort(). in second for loop we are getting index of array prior to sorting. in the last for loop we are making elements of cycle as -1

[GURMEET SINGH]

@Spindoctor the best way to understand this by taking a small array and pass through each step and note down value in different variables. This will help you to see the cycles in the array and how we are making those elements -1.

[Him]

@AnT, I agree. Specifically, I can conceive of an algorithm that involves swaps where neither item ends it's intended positions, but achieves the same number of moves. Specifically, one can make swaps to reduce any cycle to a number of two cycles (possibly ending with a single one cycle if n is odd), and then swap all of the two cycles into the correct positions. This also involves n-1 moves. Although this is not faster than the algorithm provided, it at least shows that the optimality of the provided algorithm is far from obvious.

[arax]

@AnT Minimality comes from the fact that any n-element cycle is minimally the product of n-1 transpositions

[sherelock]

Why would the complexity be n*log(n) ? Can anyone throw some intuitive light here ?

[Nitesh Bharadwaj Gundavarapu]

Counting the number of swaps in a selection sort is same as this, because it just reduce the length of cycle by one by keeping the cycle intact at each step.

[Nitesh Bharadwaj Gundavarapu]

@sherelock We just need to sort which is O(nlogn) and then count the cycles. Since each node has exactly one outgoing edge, we can do this part in O(n) by following the edges.

[Ashish Santikari]

I am not able to relate how the while loops works to find the number of cycles. Specifically, the 2nd statement in the while loop. j=arr[j]-1; Why the value of j getting derived by subtracting 1 whereas we are setting it to i at the start.

[Ryan Wood]

this doesn't seem to return the minimal number for arrays with repeat values: [8, 8, 7, 9, 9, 9, 8, 9, 7] => 6, should be 4

[Archibald]

Checked. Wrote a while ago. Yes. Doesn't work with duplicates. But. My solution fits the problem spec perfectly: "I'm working on sorting an integer sequence with no identical numbers". It was not never meant to work for the lists with duplicates. Thus shall dismiss your comment @RyanWood

[Evg]

@NiteshBharadwajGundavarapu, what to you need to sort here?

[Ajay Sharma]

the most optimal solution, others are unnecessary swapping the elements where as requirement is just to find minimum count of swaps

[John Wright]

I am thinking the reason j=arr[j]-1; @AshishSantikari can be seen by running through the code with an already sorted array. In that case, filling out the visited array, fills it out in order, with 0 being the first index, hence the -1. In that case, the while loop terminates after 1 loop each time. If out of order, the array will be temporary sparse with cycles counting how long it takes to "see" it in its correct order, which equates to the number of swaps if you subtract 1 for the 0 based indexing. Very cool.

[lissajous]

My quick analysis: | sort input array to build graph O(nlgn) with let say quicksort | build hash map to have desired index fast O(n) | build graph with hashmap O(n) | calculate strongly connected components and its size O(n) | sum according to idea O(n) | TOTAL O(nlgn)

[Dan Engel]

Just adding to @Archibald's explanation: this approach works because sorting from from the enumerated + ordered array to the original array is the same number of swaps as the opposite. I found that extra sort a little unnecessary. You can in fact get to the same result by changing the while loop to something like this (in JS): ``` while (i < enumeratedArr.length) { if (enumeratedArr[i][1] == i + 1) { i++ continue } else { swap(enumeratedArr, i, enumeratedArr[i][1] - 1) count++ } } ```

[Allan Pinkerton]

@NiteshBharadwajGundavarapu We are not sorting an arbitrary array. Sorting an array of consecutive integers starting at 1 is O(n), not O(n*logn), since for each value v, we already know it belongs in position v-1.

[Jean Valj]

take [1,2,3,4] to [4,2,3,1]