signature next_permutation c++
signature next_permutation c++
提问于 2017-05-12 09:28:37
我想知道是否有一种简单的方法可以知道由c++的std::next_permutation创建的排列的签名( parity )，根据它们的创建顺序。
int main()
{
int counter = 0;
std::vector<int> mask {0, 1, 2, 3, 4};
do
{
counter++;
// then determine the parity of permutation from knowledge of the counter
} while (std::next_permutation(mask.begin(), mask.end()));
}或者，有没有内置的函数来确定排列的奇偶性？
回答 2
Stack Overflow用户
发布于 2017-05-16 00:27:38
编辑:以下规则错误。我正在试着修复它。
看起来这里有一个很好的组合奇迹！如果您按字典顺序枚举排列(如C++标准所指定，参见例如：http://en.cppreference.com/w/cpp/algorithm/next_permutation)，那么一些实验似乎表明该符号遵循以下规则:从一个开始，然后改变符号，然后每隔一个排列改变符号。
[1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1 ...]我现在不明白为什么，但我检查了这是真的，直到*。以下是n=4示例：
([1, 2, 3, 4], 1)
([1, 2, 4, 3], -1)
([1, 3, 2, 4], -1)
([1, 3, 4, 2], 1)
([1, 4, 2, 3], 1)
([1, 4, 3, 2], -1)
([2, 1, 3, 4], -1)
([2, 1, 4, 3], 1)
([2, 3, 1, 4], 1)
([2, 3, 4, 1], -1)
([2, 4, 1, 3], -1)
([2, 4, 3, 1], 1)
([3, 1, 2, 4], 1)
([3, 1, 4, 2], -1)
([3, 2, 1, 4], -1)
([3, 2, 4, 1], 1)
([3, 4, 1, 2], 1)
([3, 4, 2, 1], -1)
([4, 1, 2, 3], -1)
([4, 1, 3, 2], 1)
([4, 2, 1, 3], 1)
([4, 2, 3, 1], -1)
([4, 3, 1, 2], -1)
([4, 3, 2, 1], 1)我想这回答了你的问题。我会尽快回来，我会找到一个解释。
Stack Overflow用户
发布于 2017-05-12 15:38:38
我不认为有这样的现有函数，但您可以使用插装实现您自己的next_permutation。类似于：
enum class Parity {Even, Odd};
Parity operator+ (Parity parity, std::size_t count)
{
return static_cast<Parity>((static_cast<std::size_t>(parity) + count) % 2);
}
template<typename It>
bool next_permutation(It begin, It end, Parity& parity)
{
if (begin == end)
return false;
It i = begin;
++i;
if (i == end)
return false;
i = end;
--i;
while (true)
{
It j = i;
--i;
if (*i < *j)
{
It k = end;
while (!(*i < *--k))
/* pass */;
std::iter_swap(i, k);
parity = parity + 1;
std::reverse(j, end);
parity = parity + std::distance(j, end) / 2;
return true;
}
if (i == begin)
{
std::reverse(begin, end);
parity = parity + std::distance(begin, end) / 2;
return false;
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43927942
复制相关文章
相似问题
腾讯云开发者
