如何有效地就地置换数组（使用 std::swap）

Question

如何就地应用排列？我的排列实际上是 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，其中所有提供的答案要么通过使用负整数 space 作弊以避免分配或输入“讨厌的“嵌套循环，将时间复杂度提高到 O(n²)。

编辑

建议前请注意std::next_permutation。我并没有尝试生成所有可能的排列，我可以用 std::next_permutation 来做。相反，我试图将单个特定排列应用于数组。

Answer 1

找到循环并排列每个循环的提示对我有用。总结一下我的方法，我在构造函数中找到了所有循环的起始索引。然后，在 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()也很容易实现，但是需要临时分配一个bit-vector.

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

如何有效地就地置换数组（使用 std::swap）

How to efficiently permute an array in-place (using std::swap)

c++

arrays

algorithm

permutation

c++17

编辑