서명 next_permutation C++

Question

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

또는 대안으로, 순열의 패리티를 결정하는 내장 함수가 있습니까?

Answer 1

그런 기존 기능이 있다고 생각하지 않지만 계측을 사용하여 직접 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; 
     } 
    } 
} 

Demo

Answer 2

편집 : 아래의 규칙이 잘못되었습니다. 나는 그것을 고치려고 노력하고있다.

여기에는 멋진 조합 기적이있는 것 같습니다. 순열을 사전 식 순서로 열거하면 (예 : 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) 

이 질문에 대한 답변으로 생각됩니다. 나는 곧 내가 여기서 설명을 찾을거야.