This content originally appeared on DEV Community and was authored by dhavalraj007
There are four kinds of permutations or combinations possible based on whether repetition is allowed or not and whether order matters or not.
All four of them are summarized and explained by example in the below figure.
To generate them using recursion we make the recursion tree.
All the combinations in this tree are the first type of permutations(n^r). if the repetitions are not allowed but the order matters then you just skip the blue ones. the point to not here is that we skipped those items here which are same as the parent node like for 2's children we skipped when 2 2 came, for 3's children we skipped when 3 3 came. So this will take care of the repetitions thing. now if the order does not matter then we cant take both 1 2 and 2 1.In the figure we skip green ones. Notice here that we only skip the children elements who are less then the parent or you can say we take elements starting from the parent itself. for example, for 1's children we start taking elements from 1 , like 1 1 ,1 2 ,1 3 for 2's children we start taking elements from 2 , like 2 2, 2 3 and for 3's children we start taking elements from 3,like 3 3.
Based on following observations here is the Cpp code
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void permComb(vector<int> data, int r, bool order, bool repeat, vector<int> out = {},int i = -1)
{
if (r == 0)
{
print(out);
return;
}
for (int next = (order?0:(i==-1?0:i)); next < data.size(); next++)
{
if (!repeat and (next == i)) continue;
out.push_back(data[next]);
r--;
permComb(data, r, order, repeat, out, next);
r++;
out.pop_back();
}
return;
}
int main()
{
vector<int> data{ 1,2,3 };
permComb(data, 2, true, false);
return 0;
}
let me know in the comments if you have any doubts.?
This content originally appeared on DEV Community and was authored by dhavalraj007
dhavalraj007 | Sciencx (2021-08-19T10:12:57+00:00) Generate all kinds of permutations and combinations using backtracking. Retrieved from https://www.scien.cx/2021/08/19/generate-all-kinds-of-permutations-and-combinations-using-backtracking/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.