All subsequences of a string of length n

Question

For a string of length 'n'. How to get all subsequences of length r (r <= n). I thought about this using dynamic programming, but could not find a good solution. I want pseudo code for this.

Eg. given the string "abc" and r = 2.

OUTPUT: ab ba ac california bc cb

early

Answer 1

It is important to see the difference between all possible substrings (continuous sequence) and usually subsequences (not necessarily contiguous).

If so, then what you requested is called combinations , and at first it’s nice to evaluate how many of them you indicated the length of your string and the size of your subsequence.

A recursive algorithm is the best approach here: it allows you to have the length of your subsequence as a variable. Here you will find a great answer in another thread .

Answer 2

This code is the standard Python library .

Answer 3

Try using the following code (in my opinion, pseudocode, but understandable):

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

Answer 4

  public static void combinations(String suffix,String prefix){ if(prefix.length()<0) return; System.out.println(suffix); for(int i=0;i<prefix.length();i++) { combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length())); } } //call above function like: combinations("","abcd"); 

Answer 5

using recursion -> choose and do not choose a concept

You have to make one decision: choose the item to add to the string or not. Based on this approach, we have a recursive solution.

 def subse(string,current,index,n): if index == n: print(current) return; else: subse(string,current+string[index],index+1,n) #pick element and add it to output string that is current subse(string,current,index+1,n) #don't pick if __name__ == "__main__": subse('abc','',0,3)