生成所有排列集-有解無憂

最近在一次采訪中，我被問到以下問題：

給定一個數字對串列，例如(2, 6)(4, 5)(1, 5)，生成所有形式為的數字241,242,243,244,245,251...。請注意，對串列的長度是可變的，即我們可以有超過 3 對數字。每對代表一個“包含區間”。例如，生成的每個數字241應該來自每個間隔：2來自第一個、4來自第二個、1來自第三個等等。重復項不作任何特殊處理，即555是有效的并且應該是輸出序列的一部分。

我想出了簡單的蠻力邏輯：

#include <iostream>
#include <vector>
using namespace std;

vector<int> res;

void helper(pair<int,int>& interval) {
  int start=interval.first;
  int end=interval.second;
  vector<int> ans;
  
  for(int i=0; i<res.size(); i  ) {
    for(int j=start; j<=end; j  ) {
      ans.push_back(res[i]*10 j);
    }
  }
  
  res=ans;
}

vector<int> generatePermutation(vector<pair<int,int>>& intervals) {
  if(intervals.empty()) return res;
  
  pair<int, int> firstInt=intervals[0];
  for(int i=firstInt.first; i<=firstInt.second; i  ) {
    res.push_back(i);
  }
 
  for(int i=1; i<intervals.size(); i  ) { 
    helper(intervals[i]);
  }
  
  return res;
}


int main() {
    vector<pair<int,int>> v;
    v.push_back({2,6});
    v.push_back({4,5});
    v.push_back({1,5});

    vector<int> ans=generatePermutation(v);
    
    for(auto& each: ans) cout<<each<<" ";

    return 0;
}

Which generates the answer as needed. But I was curious to know if there is some efficient algorithm to this problem? The interviewer did not have any time complexity on mind, although he said he was looking for a recursive solution making me think if we could perhaps solve it by backtracking in a more efficient manner.

uj5u.com熱心網友回復：

這里唯一實用的解決方案是面試官向您暗示的解決方案：遞回。

#include <iostream>
#include <vector>

void genperms(std::vector<int> &res, int n,
          std::vector<std::pair<int, int>>::const_iterator b,
          std::vector<std::pair<int, int>>::const_iterator e)
{
    if (b == e)
    {
        res.push_back(n);
        return;
    }

    n *= 10;

    for (int i=b->first; i <= b->second;   i)
        genperms(res, n i, b 1, e);
}

std::vector<int> genperms(const std::vector<std::pair<int, int>> &pairs)
{
    std::vector<int> res;

    if (!pairs.empty())
        genperms(res, 0, pairs.begin(), pairs.end());

    return res;
}

int main()
{
    auto res=genperms({{2,6}, {4, 5}, {1, 5}});

    for (auto n:res)
        std::cout << n << std::endl;
    return 0;
}

結果輸出（為簡潔起見截斷）：

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/448321.html

標籤：c algorithm

上一篇：Foor回圈列印所有元素，但是當結果保存在pandas資料幀中時，它回傳NaN

下一篇：如何解決這個嘗試迭代字串的問題？