c++ - 在 c++ 中使用 next_permutation() stl 在两个数组中进行相同的排列

Question

是否有一种简单的方法可以使 next_permutation 执行相同的一组交换相同大小的两个不同数组，例如，如果我有两个数组a[]={1,2,3,4,5}，并且b[]={12,23,21,2,3} 如果在数组 a 中的排列 1 到第三位置之后，那么数组 b 中的 12 也应该到第三位置。

Answer 1

您可以制作一个辅助索引集：

int a[] = { 1, 2, 3, 4, 5 };
int b[] = { 12, 23, 21, 2, 3 };

std::size_t indices[] = { 0, 1, 2, 3, 4 };

现在在 上执行排列indices，然后使用a[indices[i]]and b[indices[i]]。

Answer 2

请记住，std::next_permutation 不会保留任何状态（它会违背 stl 算法的概念）。那么它是如何产生下一个排列的呢？它是按照元素的顺序来完成的。这就是为什么有一个接受比较运算符的版本

如果给它一个大小为 N 的排序数组，那么 next_permutation 可以称为 N！次。否则，在算法返回 false 之前，您的排列会更少。

要回答您的问题，如果数组在上面建议的“辅助索引集”方面具有相同的顺序，那么将交换相同的元素。

例子：

int a[] = { 1, 2, 4, 3 };
int b[] = { 11, 12, 14, 13 };

这些将被排列相同，因为 sort 将产生相同的索引排序。