Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

All subsequences of a string of length n

Tags:

algorithm

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

like image 822
Keen Sage Avatar asked Dec 11 '11 19:12

Keen Sage


2 Answers

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.

like image 142
Alexander Galkin Avatar answered Oct 24 '22 11:10

Alexander Galkin


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;
}
like image 21
rendon Avatar answered Oct 24 '22 13:10

rendon