# Generating All Set Of Permutations

## 23 March 2022 - 1 answer

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.

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):

``````241
242
243
244
245
251
252

(snippola)

652
653
654
655
``````