c++ - 如何生成通过交换元素(例如 : from {0, 1,2} 到 {0,2,1})将数组更改为另一个数组的步骤？

Question

我想编写一个程序，生成一个数组到另一个数组的交换元素的步骤，(例如:从{0,1,2}到{0,2,1}，步骤是1<->2，表示交换元素1和元素2的位置)，以A={0,1,3,2}和B={2,0,3,1}为例，我原来的概念是这样的:

1. 获取A按升序排序时交换元素的步骤
2. 获取按升序排序B时交换元素的步骤
3. 交换 A 中的元素，从按照对 A 排序的步骤开始，然后按照相反顺序对 B 进行排序

这是我试过的代码:

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

输出:

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

所以从 0,1,3,2 到 2,0,3,1 的步长应该是:

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

但是当我按照步骤操作时:

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

问题是每次比较时您都打印“交换”，并且两个值的顺序不正确，这可能是不正确的，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