Generating all set of permutations-CodePudding

Recently in an interview, I was asked the following 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.

I came up with the simple brute force logic:

#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.

CodePudding user response：

The only practical solution here is the one your interviewer hinted at you: recursion.

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

Resulting output (truncated for brevity):