时间戳

首页 > 解决方案 > 寻找一种算法，给我一个给定块大小作为输入的列表的所有分区

c++ - 寻找一种算法，给我一个给定块大小作为输入的列表的所有分区

问题描述

我正在解决一个问题，该问题要求我在给定分区块的数量作为输入的情况下找到所有可能的字母组合。

这就是我的意思：

我不需要所有可能的排列，例如[ [C,A], [B,D], [F,E], [G,H,I] ] 不需要，我只需要保持字母表词典顺序的排列。我确信有一个算法可以解决这个问题——如果有人能指出我的话，那就太棒了。

标签： c++calgorithm

解决方案

你[A, B, C, D, E, F, G, H, I]在每个逗号处分开。每个逗号都可以看作是 1 到 8 范围内的一个位置。一旦选择了第一个位置，就不能再次选择它。

#include <vector>
#include <algorithm>
#include <cstdint>
#include <string>
#include <iostream>

int main(){
    std::vector<std::uint32_t> positions{1,2,3,4,5,6,7,8};
    std::vector<std::string> positionStrings;
    for(int i = 0; i < positions.size() - 2; ++i)
    {
       std::uint32_t firstPosition = positions[i];
       for(int j = i + 1; j < positions.size() - 1; ++j)
       {
          std::uint32_t secondPosition = positions[j];
          for(int k = j + 1; k < positions.size(); ++k)
          {
             std::uint32_t thirdPosition = positions[k];
             positionStrings.push_back(std::to_string(firstPosition) + "," + std::to_string(secondPosition) + "," + std::to_string(thirdPosition));
          }
       }
    }
    // You can split up the strings again by token "," and convert to numbers if needed. But this is a detail, not the algorithm which you asked for.
    for(auto string : positionStrings)
    {
        std::cout << string << std::endl;
    }
}

推荐阅读