Enumerate all matchings (tools/next_matching.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-08-13 22:46:28+09:00
• Include: #include "tools/next_matching.hpp"

template <typename RandomAccessIterator>
bool next_matching(RandomAccessIterator begin, RandomAccessIterator end);

It enumerates all the ways to divide $\{0, 1, \ldots, N - 1\}$ into $\left\lfloor \frac{N}{2} \right\rfloor$ unordered pairs and at most one remainder. It can be used as follows.

std::vector<int> a(N);
std::iota(a.begin(), a.end(), 0);
do {
  // a[0] and a[1] are a pair, a[2] and a[3] are a pair, and so on.
} while (tools::next_matching(a.begin(), a.end()));

It returns true if the next way exists, false otherwise.

Constraints

• The given sequence is a permutation of $(0, 1, \ldots, N - 1)$.

Time Complexity

• $O(N \log N)$ worst
• $O(1)$ amortized
• Note: Since the number of ways is $\left(2 \left\lfloor \frac{N - 1}{2} \right\rfloor + 1\right)!!$, it takes $O(N!!)$ time totally if you enumerate all the ways.

License

• CC0

Author

• anqooqie

Verified with

• tests/next_matching.test.cpp

Code

#ifndef TOOLS_NEXT_MATCHING_HPP
#define TOOLS_NEXT_MATCHING_HPP

#include <iterator>
#include <cassert>
#include <algorithm>

namespace tools {
  template <typename RandomAccessIterator>
  bool next_matching(RandomAccessIterator begin, RandomAccessIterator end) {
    const auto N = ::std::distance(begin, end);
    // assert(::tools::mex(begin, end) == N);
    if (N <= 2) return false;

    auto l = (N - 2) / 2 * 2;
    for (; l > 0 && begin[l - 1] > begin[l + 1]; l -= 2);
    ::std::sort(::std::next(begin, l), ::std::prev(end, N % 2));

    if (l == 0) {
      if (N % 2 == 0) return false;
      if (begin[N - 1] == 0) {
        ::std::rotate(begin, ::std::prev(end), end);
        return false;
      }
      ::std::iter_swap(::std::next(begin, begin[N - 1] - 1), ::std::prev(end));
      return true;
    }

    ::std::iter_swap(::std::next(begin, l - 1), ::std::upper_bound(::std::next(begin, l), ::std::prev(end, N % 2), begin[l - 1]));
    return true;
  }
}

#endif

#line 1 "tools/next_matching.hpp"



#include <iterator>
#include <cassert>
#include <algorithm>

namespace tools {
  template <typename RandomAccessIterator>
  bool next_matching(RandomAccessIterator begin, RandomAccessIterator end) {
    const auto N = ::std::distance(begin, end);
    // assert(::tools::mex(begin, end) == N);
    if (N <= 2) return false;

    auto l = (N - 2) / 2 * 2;
    for (; l > 0 && begin[l - 1] > begin[l + 1]; l -= 2);
    ::std::sort(::std::next(begin, l), ::std::prev(end, N % 2));

    if (l == 0) {
      if (N % 2 == 0) return false;
      if (begin[N - 1] == 0) {
        ::std::rotate(begin, ::std::prev(end), end);
        return false;
      }
      ::std::iter_swap(::std::next(begin, begin[N - 1] - 1), ::std::prev(end));
      return true;
    }

    ::std::iter_swap(::std::next(begin, l - 1), ::std::upper_bound(::std::next(begin, l), ::std::prev(end, N % 2), begin[l - 1]));
    return true;
  }
}

Back to top page