算法：如何从一组数据种提取出需要的组合

Question

例如，有如下的十六进制数据：

27 2c 30 46 48 50 61 73 82 93 a3 aa b3 c4 d3 e5 f3 106 113 127 133 148 153

高位为index（这部分为数据中的特征值），低四位为数据。以上数据中，27和2c只要一个，46和48也只要一个，a3和aa也只要一个，但必须每种组合都要有。

提取的其中一组数据如下：

27 30 48 50 61 73 82 93 a3 b3 c4 d3 e5 f3 106 113 127 133 148 153

Answer 1

模仿next_premutation写的非递归版：

思路：
首先算出每个位置上的可能元素。
然后用进位的算法依次向后进位。

#include <iostream>
#include <tuple>
#include <vector>

template <class ForwardIt>
auto GetFirstCombination(ForwardIt first, ForwardIt last) {
  std::vector<std::tuple<ForwardIt, ForwardIt, ForwardIt> > it_pair; // begin, curr, end
  auto Equal = [](auto x, auto y){
        return static_cast<uint64_t>(x)>>4 == static_cast<uint64_t>(y)>>4;
      };

  while (first != last) {
    auto curr = first;
    auto next = std::next(curr);
    while (next!=last && Equal(*curr, *next)) {
      ++curr;
      ++next;
    }
    
    it_pair.emplace_back(first, first, curr);
    first = next;
  }

  return it_pair;
}

template <class ForwardIt>
bool NextCombination(ForwardIt first, ForwardIt last) {
  for (; first!=last; ++first) {
    if (std::get<0>(*first) == std::get<2>(*first)){
      ;
    } else if (std::get<1>(*first) == std::get<2>(*first)) {
      std::get<1>(*first) = std::get<0>(*first);
    } else {
      ++std::get<1>(*first);
      break;
    }
  }
  
  return first != last;
}

int main() {
  std::vector<uint32_t> input = {0x01, 0x03, 0x07, 0x23, 0x25, 0x70, 0x80};
  auto result = GetFirstCombination(input.begin(), input.end());

  std::cout << std::hex;
  do {
    for (const auto &ele : result)
      std::cout << *std::get<1>(ele) << " ";
    std::cout << std::endl;
  } while (NextCombination(result.begin(), result.end()));

  return 0;
}