使用C++中的next_permutation() STL，在两个数组中找到相同的排列

Question

有没有一种简单的方法让next_permutation在两个相同大小的不同数组中执行相同的交换操作呢？ 例如，如果我有两个数组a[]={1,2,3,4,5}和b[]={12,23,21,2,3}， 如果在a数组中，第一个位置的元素被置换到了第三个位置，那么b数组中的12也应该被置换到第三个位置。

- ka4tik

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]]和b[indices[i]]。

- Kerrek SB

Answer 2

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

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

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

例如：

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

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

- killogre