All subsequences of a string of length n

Question

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

Answer 1

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.

Answer 2

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