如何有效地在适当的位置排列数组(使用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时的预计算步骤中。我希望就地排列能快速进行，从外观上看，要求根本不分配额外内存将导致一些严重的性能牺牲。

我特别引用了在恒定内存空间中应用排列的算法，其中所有提供的答案要么通过使用负整数空间来作弊以避免分配，要么输入"；讨厌的"；嵌套循环将时间复杂性提高到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()也很容易实现，但需要临时分配比特向量。

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