Given a string of length 'n'. How do I get all the sub sequences of length r(r<=n). I was thinking of doing it using dynamic programming but could not come up with a good solution. I want a pseudo code for this.
Eg. given the string "abc" and r = 2.
OUTPUT : ab ba ac ca bc cb
thanks in advance
It is important to see the difference between all possible substrings (contiguous sequence) and generally subsequences (not necessarily contiguous).
If this is true, then what you were asked is called combinations, and it is nice first to estimate how many of them you have given the length of your string and the size of your subsequence.
A recursive algorithm is the best approach here: it allows you to have a the length of your subsequence as a variable. You will find a perfect answer in another thread here.
Try the following code(no pseudo code but understandable, I hope):
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
string S;
int n;
vector<string> L;
void F(int index, int length, string str)
{
if (length == 0) {
L.push_back(str);
} else {
for (int i = index; i < n; i++) {
string temp = str;
temp += S[i];
F(i + 1, length - 1, temp);
}
}
}
int main()
{
S = "abcde"; // replace with your string
n = S.length();
int k = 3; // or what you want
F(0, k, string(""));
int count = 0;
for (int i = 0; i < int(L.size()); i++) {
string temp = L[i];
sort(temp.begin(), temp.end());
do {
cout << temp << endl;
count++;
} while (next_permutation(temp.begin(), temp.end()));
}
cout << endl << "count = " << count << endl;
return 0;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With