如何使用另一个向量来排序向量？

Question

这个问题与这里提出的问题类似，然而，这个答案对我的问题无效，而且稍有不同。

我试图做的最好通过代码展示：

//this would be a copy version:
int main(){
   std::vector<uint32_t> order = {0,2,5,6,9,10,1,3,4,7,8,11};
   std::vector<uint32_t> example = {0,1,2,3,4,5,6,7,8,9,10,11};
   std::vector<uint32_t> output(order.size());
   for(uint32_t i = 0; i < order.size(); ++i){
       output[i] = example[order[i]];
   }
}
//output comes out to {0,2,5,6,9,10,1,3,4,7,8,11}

然而，当我尝试使用上述链接中的重新排序代码来实现原地版本时：

void reorder(std::vector<uint32_t> &v, std::vector<uint32_t> const &order )  {   
    for ( int s = 1, d; s < order.size(); ++ s ) {
        for ( d = order[s]; d < s; d = order[d] ) ;
        if ( d == s ) while ( d = order[d], d != s ) std::swap( v[s], v[d] );
    }
}

int main(){
    std::vector<uint32_t> order = {0,2,5,6,9,10,1,3,4,7,8,11};
    std::vector<uint32_t> example = {0,1,2,3,4,5,6,7,8,9,10,11};
    reorder(example, order);
}
//example = {0,6,1,7,8,2,3,9,10,4,5,11,}

我如何在不复制内存的情况下实现我正在尝试完成的就地版本？

编辑

我想要更清楚一些，代码中的向量 example 可以是任意元素，我只是偶尔使用了特定的初始化方式以便于检查。以下示例完全有效：

std::vector<uint32_t> example = {300,12,21,34,47,15,61,57,82,94,1,2};

• order和example始终包含相同数量的元素。
• 不能保证order和example存储相同的数据类型。
• 可以确保order存储唯一值。
• 可以确保order始终是uint32_t数据类型。
• order的范围始终为0到n-1，其中n是example的大小，每个数字仅出现一次，并且不超出该范围（就像示例代码中一样）。
• 该范围的实际顺序完全随机，与偶数或奇数索引无关，也不按任何顺序。

- Sam Moldenha

---

如果你不想要一个完全通用的解决方案，你可以认识到这两个向量具有相同的长度，包含相同的类型，并且order中的所有值都是唯一且有效的索引。然后，你可以逐个元素地交换order中的内容和std::swap(order[i], example[order[i]]);，然后再执行std::swap(example, order);。然而，这确实需要order是非常量的，同时还需要满足其他所有条件。 - paddy

当一个问题有多个答案时，你如何测试“重新排序代码”这个问题？而且它还被标记为另一个问题的重复！在尝试了所有提供的解决方案之前，你不能声称它们无法解决你的问题。 - Mark Ransom

order和example包含的元素数量是保证相同的吗？order和example存储的数据类型是保证相同的吗？order中的每个索引都是唯一的吗？您在回答中提供了更新，但是没有澄清这些问题。 - paddy

@paddy 希望这次修改能更加明确事情。 - Sam Moldenha

订单也可以是任意的吗？这个例子有一个很好的顺序，有时被称为unshuffle、unzip或者uninterlace。 - harold

Answer 1

我想出了一个简单的算法，可以在O(N)时间复杂度和O(1)额外存储空间下完成。毫不奇怪，这会破坏order的内容。我认为如果不增加时间复杂度或存储复杂度，你无法避免这种情况。

template <typename T>
void reorder(std::vector<T> &v, std::vector<uint32_t> &order)
{
    for (size_t i = 0; i < v.size(); i++)
    {
        size_t next = order[i];      // find index of next output
        while (next < i)             // resolve chain of moves
        {
            next = order[next];
        }
        std::swap(v[i], v[next]);    // exchange data
        order[i] = next;             // record where previous data moved to
    }
}

基本方法是一次迭代通过排序，考虑当前位置之前的每个位置都已解决。您永远不会修改已解决位置的排序或数据。

除了order是一个排序向量的平凡情况外，您必须将某个数据移到一边，以便在该位置引入所需值。有两种可能的情况：

1. 该值已经在正确的位置上，或者位于某个“未来”位置；或者
2. 该值指向一个“过去”位置，因此我们知道它已经移动了一次或多次，现在位于“未来”位置。

因此，在非常基本的层面上，当您发现对于某个i，order[i]的值小于i时，您就知道它已被移动，并且它移动到位置order[order[i]]。从那个位置，它可能又被移动了。通过应用完全相同的测试，您将得到一个大于或等于i的索引。这就是数据移动到的位置。

这个O(N)的秘密在于，在解决最终的“移动到”位置之后，你还要进行一步最后的操作，即用新位置覆盖order[i]。这意味着无论在这个位置上你需要做多少次搜索，都不会重复。

现在，很明显这样做会导致线性时间复杂度，所以如果你觉得有点费解也不要感到难过。我自己也很难说服自己，事实上，在写这个答案之前，我不得不通过寻找order的所有排列的最坏情况总搜索次数来进行实验验证。这也有助于验证算法的正确性。

推理的关键在于，一个值所做的“跳跃”越多，其他值可能的跳跃就越少。通过折叠任何搜索的结果，你确保该搜索在未来也是O(1)的。至关重要的是，这意味着链式一次额外跳跃的过程也是O(1)，因为对于相同的数据值，连续的“跳跃”将始终指向在数据移动时被压缩的搜索。

---

这是一个小的测试工具，用于验证所有排列并计算执行的搜索间接引用的总数。

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

typedef int Data;

template <typename T>
size_t reorder(std::vector<T> &v, std::vector<uint32_t> &order)
{
    size_t indirections = 0;
    for (size_t i = 0; i < v.size(); i++)
    {
        size_t next = order[i];
        while (next < i)
        {
            // std::cout << "search " << i << " : hop to " << next << "\n";
            next = order[next];
            indirections++;
        }
        std::swap(v[i], v[next]);
        order[i] = next;
    }
    return indirections;
}

size_t count_worst_case_indirections(size_t size)
{
    size_t max_indirections = 0;

    std::vector<uint32_t> order_perm(size);
    std::vector<uint32_t> order_worst;
    std::vector<uint32_t> order;
    std::vector<Data> data(size);
    std::vector<Data> expected;
    expected.reserve(size);

    // Test all possible orderings
    std::iota(order_perm.begin(), order_perm.end(), 0);
    do
    {
        // Reset initial data and generate expected result
        order = order_perm;
        std::iota(data.begin(), data.end(), 0);
        expected.clear();
        for (auto i : order) expected.push_back(data[i]);

        // Run test
        size_t indirections = reorder(data, order);
        if (indirections > max_indirections)
        {
            max_indirections = indirections;
            order_worst = order_perm;
        }

        // Throw if result is invalid
        if (data != expected) throw "ALGORITHM IS BROKEN";
    } while (std::next_permutation(order_perm.begin(), order_perm.end()));

    std::cerr << "worst order : ";
    for (auto x : order_worst) std::cerr << x << ' ';
    std::cerr << "\n";

    return max_indirections;
}

int main()
{
    for (size_t size = 1; size < 12; size++)
    {
        size_t max_indirections = count_worst_case_indirections(size);
        std::cout << "Size " << size << " : " << max_indirections << "\n";
    }
}

stdout:

Size 1 : 0
Size 2 : 1
Size 3 : 2
Size 4 : 3
Size 5 : 4
Size 6 : 5
Size 7 : 6
Size 8 : 7
Size 9 : 8
Size 10 : 9
Size 11 : 10

错误输出：

worst order : 0 
worst order : 1 0 
worst order : 1 2 0 
worst order : 1 2 3 0 
worst order : 1 2 3 4 0 
worst order : 1 2 3 4 5 0 
worst order : 1 2 3 4 5 6 0 
worst order : 1 2 3 4 5 6 7 0 
worst order : 1 2 3 4 5 6 7 8 0 
worst order : 1 2 3 4 5 6 7 8 9 0 
worst order : 1 2 3 4 5 6 7 8 9 10 0

这在搜索中显然是最坏情况的O(N)。如果你在reorder函数中注释掉order[i] = next;这一行，你会看到最坏情况变为O(N²)。

然后，如果你使用一个最坏情况排序的单次实验（有很多最坏情况排序），并取消搜索循环中的输出行的注释，你将明确地看到为什么将搜索扁平化是重要的。

- paddy

---

赢家。我投降。 - selbie

哈哈，好吧，如果这是一场战斗的话，下次我一定会加入一些激烈的嘲讽和一些假线索！！;) 开玩笑的，这个问题真的让我很困扰，所以我很高兴找到了解决办法，这样我就可以继续我的生活了。很棒的是，它竟然适合动态规划，并且比我最初预想的时间复杂度要好。 - paddy

这是一个非常棒的算法。如果我再稍微不那么诚实一点，我会忍不住设立一个马甲账号来给它再点赞。 - Jerry Coffin

Answer 2

我在第一次回答时误解了你的问题。所以我删除了那个答案，现在重新提交。

基本上，如果你需要避免复制数组，那也意味着你不能使用哈希表（映射）来解决连续重新排序的问题。因此，就地重新排序成为一个O(N²)的运行时算法，除了已经分配的存储空间外，不需要额外的O(1)存储空间。

void reorder(std::vector<uint32_t>& items, std::vector<uint32_t>& order)
{

    // n-squared without additional storage
    for (uint32_t i = 0; i < (uint32_t)items.size(); i++)
    {
        if (order[i] == i)
        {
            continue;
        }

        // keep track of the displacement that's about to be done
        uint32_t displacedValue = items[i];
        uint32_t availableIndex = order[i];

        // swap
        items[i] = items[availableIndex];
        items[availableIndex] = displacedValue;

        // scan ahead in orders array to account for the swap
        for (size_t j = i + 1; j < items.size(); j++)
        {
            if (order[j] == i)
            {
                order[j] = availableIndex;
            }
        }
    }
}

Note that the above code will permute and corrupt the `order` table.

证明概念使用您的示例：

int main() {
    std::vector<uint32_t> order = { 0,2,5,6,9,10,1,3,4,7,8,11 };
    std::vector<uint32_t> example = { 0,1,2,3,4,5,6,7,8,9,10,11 };

    reorder(example, order);

    // show the final sort order as applied
    for (size_t i = 0; i < example.size(); i++) {
        std::cout << example[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

以上打印结果为：0 2 5 6 9 10 1 3 4 7 8 11 备选方案 如果您能够承担存储成本，即在不复制example的情况下复制order，则可以将上述代码转换为运行时间和存储空间均为O(N)的解决方案。

void reorder2(std::vector<uint32_t>& items, std::vector<uint32_t>& order) {

    // create a reverse lookup table on order
    std::unordered_map<uint32_t, uint32_t> reverseLookup; // reverse of order table
    for (uint32_t i = 0; i < (uint32_t)items.size(); i++)
    {
        reverseLookup[order[i]] = i;
    }

    for (uint32_t i = 0; i < (uint32_t)items.size(); i++)
    {
        if (order[i] == i)
        {
            continue;
        }

        // keep track of the displacement that's about to be done
        uint32_t displacedValue = items[i];
        uint32_t availableIndex = order[i];

        // swap
        items[i] = items[availableIndex];
        items[availableIndex] = displacedValue;

        // account for the swap
        uint32_t j = reverseLookup[i];
        order[j] = availableIndex;
        reverseLookup[availableIndex] = j;
    }
}

- selbie

---

我有一种直觉，认为在每个步骤中，必定存在一种巧妙而不明显的方法来重新利用已处理过的order部分，并结合一个O(logN)的机制来确定需要移动的值如何重新排序... 有点像堆。但是我的大脑无法胜任这个任务。我无法接受没有一种原地O(N.logN)解决方案和O(1)存储空间的存在。 - paddy

@paddy - 昨晚我在为这个问题努力解决时，我也有同样的想法。今晚我可能会再试一次。如果你能找到有效的解决方案，请随时提交你自己的答案。我可能会给它点赞！ - selbie

是的，我昨天试了一下，但失败了。实际上，我当时走在正确的轨道上，但由于某种原因忽略了一个细节。今天以更清醒的头脑弄明白了，结果发现这可以在O(N)时间内完成 :) 解决方案非常简单，但对我这样的人来说并不立即显而易见！ - paddy