相关疑难解决方法(0)

例如,输入是

Array 1 = [2, 3, 4, 5]
Array 2 = [3, 2, 5, 4]

需要的最小交换次数是2.

交换不需要与相邻的单元相交,任何两个元素都可以交换.

可能重复:
计算将一个排列转换为另一个排列所需的交换

我正在寻找一种计算某种字符串距离的算法,其中只允许操作是两个相邻字符的转置.例如:
string1:"mother"
string2:"moterh"
距离:2(首先交换"h"与"e"并获得"motehr"然后"h"与"r"导致"moterh")
我知道Damerau -Levenshtein距离这个问题非常相似,但它需要大量的内存(我希望它可以在高达1 000 000个字符的单词上工作得非常快).我已经写过:

int amo = 0;

for (int i = 0; i < n; i++)
{
    if (fromString[i] == toString[i])
        continue;
    char toWhat = toString[i];
    int where = -1;
    for (int j = i; j < n; j++)
    {
        if (fromString[j] == toWhat)
        {
            where = j;
            break;
        }
    }
    while (where != i)
    {
        char temp = fromString[where];
        fromString[where] = fromString[where - 1];
        fromString[where - 1] = temp;
        where--;
        amo++;
    } …

我知道如何对一对矢量进行排序,但是你如何对一对矢量进行排序？我可以考虑在一对向量上编写一个自定义的"虚拟"迭代器并对其进行排序,但这看起来非常复杂.有没有更简单的方法？C++ 03中有一个吗？我想用std::sort.

当处理在硬件中生成的一些数据时出现这个问题,其中一对数组比对数组更有意义(从那时起会出现各种步幅和对齐问题).我意识到,否则保持一对向量而不是对的向量将是一个设计缺陷(数组问题的结构).我正在寻找一个快速的解决方案,将数据复制到成对的向量然后返回(我将它返回到HW以进行更多处理)不是一个选项.

例:

keys   = {5, 2, 3, 1, 4}
values = {a, b, d, e, c}

排序后(通过第一个向量):

keys   = {1, 2, 3, 4, 5}
values = {e, b, d, c, a}

我将"一对矢量"称为一对keys和values(存储为例如std::pair<std::vector<size_t>, std::vector<double> >).矢量具有相同的长度.

是否有一种有效的算法(在大O表示法方面有效)来找到交换数量以将置换P转换为身份置换I？交换不需要在相邻元素上,而是在任何元素上.

例如:

I = {0, 1, 2, 3, 4, 5}, number of swaps is 0
P = {0, 1, 5, 3, 4, 2}, number of swaps is 1 (2 and 5)
P = {4, 1, 3, 5, 0, 2}, number of swaps is 3 (2 with 5, 3 with 5, 4 with 0)

一个想法是编写这样的算法:

int count = 0;
for(int i = 0; i < n; ++ i) {
    for(; P[i] != i; ++ count) { // could be permuted multiple …