生成所有排列组合

Question

最近在接受采访时，有人问我以下问题：

Given a list of pairs of numbers, like (2, 6)(4, 5)(1, 5), generate all numbers of the form 241,242,243,244,245,251.... Note that the length of list of pairs is variable, i.e., we could have more than 3 pairs of numbers. Each pair represents an "inclusive interval". Each of the numbers generated, for e.g., 241 should come from each of the intervals: 2 from the first, 4 from the second, 1 from the third and so on. Duplicates are not to be treated any specially, i.e., 555 is valid and should be part of the output sequence.

我想到了简单的暴力逻辑：

#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;
}

生成答案 as needed。但是我很想知道这个问题是否有一些有效的算法？面试官并没有考虑任何时间复杂度，尽管他说他正在寻找一种递归解决方案，这让我想我们是否可以通过更有效的方式回溯来解决它。

Answer 1

这里唯一实用的解决方案是您的面试官向您暗示的解决方案：递归。

#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;
}

结果输出（为简洁起见被截断）：

生成所有排列组合

Generating all set of permutations

c++

algorithm