How to generate the steps of changing an array into another array by swapping elements (eg: from {0,1,2} to {0,2,1})?

Question

I want to create a program to generate the steps of swapping elements during changing an array to another array,(eg:from {0,1,2} to {0,2,1}, the step is 1<->2, which means swap the position of element 1 and element 2),taking A={0,1,3,2} and B={2,0,3,1} as example, my original concept is as following:

1. get the steps of swapping elements during sorting A in asending order
2. get the steps of swapping elements during sorting B in asending order
3. swap the elements in A, starting from following the steps to sort A, then follow the steps to sort B but in reverse order

it is the code I tried:

#include <stdlib.h>
#include <functional>
#include <vector>
int main(){
    std::function<bool(int,int)> f=[](int a,int b){
        if(a>=b)
            printf("%d<->%d\n",a,b);
        return a<b;
    };
    std::vector<int> a={0,1,3,2};
    std::sort(a.begin(),a.end(),f);
    printf("---\n");
    std::vector<int> b={2,0,3,1};
    std::sort(b.begin(),b.end(),f);
    return 0;
}

output:

1<->0 //step to sort A
3<->1
2<->1
---
3<->0 //step to sort B
3<->2
1<->0

so the step to change from 0,1,3,2 to 2,0,3,1 should be:

1<->0
3<->1
2<->1
1<->0
3<->2
3<->0

but when I follow the step:

0,1,3,2
1,0,3,2
3,0,1,2
3,0,2,1
3,1,2,0
2,1,3,0
2,1,0,3

the result is 2,1,0,3 instead of 2,0,3,1, why? Is my concept to generate the step wrong? if so, is there other way to generate the step to change an array to another array by swapping position?

Answer 1

The problem is that you are printing a "swap" each time there is a comparison and the two values are not in the right order, this is probably not correct, the std::sort algorithm may do check without swapping. You can use a custom Int structure to test:

struct Int {
    Int(int v) : v_(v) { }
    Int(const Int&) = default;
    Int& operator=(const Int& o) {
        std::cout << v_ << " <- " << o.v_ << '\n'; 
        v_ = o.v_;
        return *this;
    }
    int v_;
};

bool operator<(const Int& lhs, const Int& rhs) {
    return lhs.v_ < rhs.v_; 
}

Then:

int main(){
    std::vector<Int> a{0,1,3,2};
    std::cout << "Sorting A:\n";
    std::sort(a.begin(),a.end());
    std::cout << '\n';
    std::vector<Int> b={2,0,3,1};
    std::cout << "Sorting B:\n";
    std::sort(b.begin(),b.end());
    return 0;
}

Output is:

Sorting A:    Sorting B:
1 <- 1        0 <- 2
3 <- 3        2 <- 0
2 <- 3        3 <- 3
3 <- 2        1 <- 3
              3 <- 2
              2 <- 1

Which gives you the various assignment - Note that std::sort implementation may be optimized for such small ranges, meaning that you do not have only swap (e.g. in the above, for B, you get 1, 2 and 3 swapped "together").

So what you would need to do would be (without the useless a <- a):

2 <-> 3
2 -> 1
3 -> 2
1 -> 3
0 <-> 2

And then you need to transform this in only binary swap:

2 <-> 3
2 <-> 1
1 <-> 3
0 <-> 2

---

If you want to get the binary swap directly, you can get a bit more ugly (hoping your computer is gentle with this UB) and:

struct Int {
    Int(int v) : v_(v) { }
    Int(const Int&) = default;
    Int& operator=(const Int& o) {
        if (v_ != o.v_) 
            std::cout << v_ << " <-> " << o.v_ << '\n'; 
        std::swap(v_, o.v_);
        return *this;
    }
    mutable int v_;
};

Output:

Sorting A:    Sorting B:
2 <-> 3       0 <-> 2
              1 <-> 3
              1 <-> 2

Combined:

2 <-> 3
1 <-> 2
1 <-> 3
0 <-> 2

Answer 2

If the values in the array(s) are guaranteed to be unique, then a better approach is the following:

1. Detect the final position of each element by looking at the target array and store that information in a map M (not necessarily a std::map, it can also be an std::unordered_map, or a sorted std::vector of (value, target-index) pairs).

2. For each position in the source array keep swapping the element at the current position into its target position (obtained from M) until the element that appears in the current position corresponds to its target position.

This approach minimizes the count of required swaps. For example, the array {0, 4, 3, 2, 1, 5} can be turned into {5, 4, 3, 2, 1, 0} with a single swap of the first and last elements, whereas your approach would generated a long sequence of swaps taking the source array to the destination array through an intermediate ascendingly sorted state {0, 1, 2, 3, 4, 5}.

In particular, in your example the desired permutation can be achieved with just two swaps:

       # 0,1,3,2
0<->1  # 1,0,3,2
0<->3  # 2,0,3,1

C++ implementation:

#include <stdlib.h>
#include <vector>
#include <map>

int main(){
    std::vector<int> a={0,1,3,2};
    std::vector<int> b={2,0,3,1};
    std::map<int, int> m;

    for ( int i = 0; i < b.size(); ++i )
        m[b[i]] = i;

    for ( int i = 0; i < a.size(); ++i )
    {
        for ( ; ; )
        {
            const int t = m[a[i]];
            if ( i == t )
                break;

            printf("%d<->%d\n", i, t);
            std::swap(a[i], a[t]);
        }
    }
    return 0;
}