首页 > 开发 > C++ > 正文

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

2017-09-11 21:23:09  来源: 网友分享

例如,有如下的十六进制数据:

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

高位为index(这部分为数据中的特征值),低四位为数据。以上数据中,272c只要一个,4648也只要一个,a3aa也只要一个,但必须每种组合都要有。

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

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

解决方案

模仿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;}