代码之家 › 专栏 › 技术社区 › Jan Schultke

如何就地排列数组(使用std::swap)

permutation c++17 algorithm arrays c++

Jan Schultke · 技术社区 · 4 年前

如何在适当的位置应用排列?我的排列是有效的 size_t[] 哪里 perm[i] 表示输入索引的目标索引 i .

如果我有一个输入和输出数组,我知道如何应用排列:

struct Permutation {
    std::vector<size_t> perm;

    template <typename T>
    void apply(const T in[], T out[]) const
    {
        for (size_t i = 0; i < size(); ++i) {
            out[i] = std::move(in[perm[i]]);
        }
    }

}

但是,我只想用一个数组来实现这一点,类似于 std::sort 有效,所以只要使用 std::swap 到目前为止,我的想法是:

struct Permutation {
    std::vector<size_t> perm;

    template <typename T>
    void apply(T data[]) const
    {
        for (size_t i = 0; i < size(); ++i) {
            std::swap(data[i], data[perm[i]]);
        }
    }

}

但这行不通。例如:

Permutation perm = {2, 1, 0};
char data[] {'a', 'b', 'c'};
perm.apply(data);

// because I swap indices 0 and 2 twice, I end up with the input array
data == {'a', 'b', 'c'};

那么,如何正确地排列一个数组呢?如果分配了额外的内存也没关系,只要在 Permutation 是建造的。我希望就地排列能迅速发生,从外观上看,我要求不分配额外的内存将导致严重的性能损失。

我特别提到 Algorithm to apply permutation in constant memory space 哪里 全部的 在提供的答案中,要么使用负整数空间来避免分配,要么输入“讨厌的”嵌套循环,将时间复杂度放大到O(n)。

编辑

建议前请注意 std::next_permutation .我不是在尝试生成所有可能的排列,我可以用 std::下一个排列 .相反,我尝试对数组应用一个特定的排列。

0 回复 | 直到 4 年前

Jan Schultke 4 年前

找到循环并排列每个循环的提示对我很有用。总结我的方法,我在构造函数中找到所有循环的开始索引。然后,在 apply() ,我通过反复使用 std::swap .

struct Permutation {
private:
    /// The single vector which stores both the permutation
    /// AND the indices of the cycles starts.
    std::vector<size_t> perm;
    /// The size of the permutation / index of first cycle index.
    size_t permSize;

public:
    Permutation(std::vector<size_t> table)
        : perm{std::move(table)}, permSize{perm.size()} {
        findCycles();
    }

    template <typename T>
    void apply(T data[]) const {
        for (size_t cycle = permSize; cycle < perm.size(); ++cycle) {
            const size_t start = perm[cycle];
            for (size_t prev = start, next = perm[prev];
                 next != start;
                 prev = next, next = perm[next]) {
                std::swap(data[prev], data[next]);
            }
        }
    }

    size_t size() const {
        return permSize;
    }

private:
    void findCycles();
}

findCycles() 也很容易实现,但需要临时分配位向量。

void Permutation::findCycles() {
    std::vector<bool> visited(size());

    for (size_t i = 0; i < size(); ++i) {
        if (visited[i]) {
            continue;
        }
        for (size_t j = i; not visited[j]; ) {

            visited[j] = true;
            j = perm[j];
        }
        perm.push_back(i);
    }
}