How to generate steps for changing an array to another array by replacing elements (for example: from {0,1,2} to {0,2,1})?

Question

I want to create a program for generating steps of swap elements when changing an array to another array (for example: from {0,1,2} to {0,2,1}, step 1 ↔ 2, which means replacing the position of element 1 and element 2) taking as an example A = {0,1,3,2} and B = {2,0,3,1}, my initial concept is this:

• get steps to replace items while sorting A in the order they are added
• get the steps to replace items while sorting B in order of addition
• replace the elements in A starting from the following steps to sort A, then follow the steps to sort B, but in reverse order

this 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

therefore, the step for changing 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

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

Answer 1

, "swap" , , , , , , std::sort . Int :

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_; 
}

:

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;
}

:

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

- , std::sort , , (, , B, 1, 2 3 "" ).

( a <- a):

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

:

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

---

, (, UB) :

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_;
};

:

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

:

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

Answer 2

(-) , :

• , M ( std::map, std::unordered_map, std::vector (value, target-index)).

• ( M), , , .

. , {0, 4, 3, 2, 1, 5} {5, 4, 3, 2, 1, 0} , , {0, 1, 2, 3, 4, 5}.

, :

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

++:

#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;
}