combinations.hpp¶

SECTIONUtility INCLUDEnoya/combinations.hpp

按字典序枚举所有 \(k\) 元子集，枚举对象为整数 0 到 \(n-1\)，并允许回调提前停止。

Complexity: Time: O(k) per emitted k-subset. Space: O(k).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(k) per emitted k-subset.
/// Space: O(k).

#include <cassert>
#include <vector>

namespace noya {

/// @brief Enumerate all increasing k-subsets of [0,n) in lexicographic order,
/// invoking callback(span-like vector); stop early when it returns false.
template <class Callback>
void enumerate_combinations(int n, int k, Callback f) {
  assert(0 <= k && k <= n);
  std::vector<int> sel(k);
  for (int idx = 0; idx < k; idx++) {
    sel[idx] = idx;
  }
  if (k == 0) {
    f(sel);
    return;
  }
  while (true) {
    if (!f(sel)) {
      return;
    }
    int idx = k - 1;
    while (idx >= 0 && sel[idx] == n - k + idx) {
      idx--;
    }
    if (idx < 0) {
      return;
    }
    sel[idx]++;
    for (int nxt = idx + 1; nxt < k; nxt++) {
      sel[nxt] = sel[nxt - 1] + 1;
    }
  }
}

} // namespace noya

#ifndef NOYA_COMBINATIONS_HPP
#define NOYA_COMBINATIONS_HPP 1

/// @complexity Time: O(k) per emitted k-subset.
/// Space: O(k).

#include <cassert>
#include <vector>

namespace noya {

/// @brief Enumerate all increasing k-subsets of [0,n) in lexicographic order,
/// invoking callback(span-like vector); stop early when it returns false.
template <class Callback>
void enumerate_combinations(int n, int k, Callback f) {
  assert(0 <= k && k <= n);
  std::vector<int> sel(k);
  for (int idx = 0; idx < k; idx++) {
    sel[idx] = idx;
  }
  if (k == 0) {
    f(sel);
    return;
  }
  while (true) {
    if (!f(sel)) {
      return;
    }
    int idx = k - 1;
    while (idx >= 0 && sel[idx] == n - k + idx) {
      idx--;
    }
    if (idx < 0) {
      return;
    }
    sel[idx]++;
    for (int nxt = idx + 1; nxt < k; nxt++) {
      sel[nxt] = sel[nxt - 1] + 1;
    }
  }
}

} // namespace noya

#endif // NOYA_COMBINATIONS_HPP

#include <cassert>
#include <vector>

/// @complexity Time: O(k) per emitted k-subset.
/// Space: O(k).

namespace noya {

/// @brief Enumerate all increasing k-subsets of [0,n) in lexicographic order,
/// invoking callback(span-like vector); stop early when it returns false.
template <class Callback>
void enumerate_combinations(int n, int k, Callback f) {
  assert(0 <= k && k <= n);
  std::vector<int> sel(k);
  for (int idx = 0; idx < k; idx++) {
    sel[idx] = idx;
  }
  if (k == 0) {
    f(sel);
    return;
  }
  while (true) {
    if (!f(sel)) {
      return;
    }
    int idx = k - 1;
    while (idx >= 0 && sel[idx] == n - k + idx) {
      idx--;
    }
    if (idx < 0) {
      return;
    }
    sel[idx]++;
    for (int nxt = idx + 1; nxt < k; nxt++) {
      sel[nxt] = sel[nxt - 1] + 1;
    }
  }
}

} // namespace noya