Subsequence generation recursively and iteratively.

 Generating all subsequences of the a sequence iteratively and recursively.

Given a string we want to generate all subsequences of the string.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.A subsequence is not necessarily contiguous.

For example suppose we have a string "abcd" so "abd","bd","bc" are all subsequences of string but "ba"

"dba" are not since in them the order of characters are shuffled.So we have to retain the order of indexes.

So we begin with algorithm to generate all subsequences and then we will see how each subsequence is being generated.

Let's consider an array with 3 elements {1,2,3}.To generate a subsequence we need to consider every index ,either that index belong to the subsequence or not.Hence for every index we have 2 choices and if there are n elements in the array ,to form a subsequence we need to consider one of 2 choices.

So total subsequence=2*2*....*2   (n times) =2^n.

So we need to consider the index of the original array and whether to include it in the subsequence.if we include the element size increases by one else doesn't.

Now lets see recursive calls for {1,2,3}.

The arrows number show which function will be called at which number.Lower number will be called first.

But the subsequences can also be generated iteratively.A binary string of length n  can be used for this.0 means not to include the element in the subsequence and 1 means include it.It's easy to visualise. Say for an array={1,2,3} we need a binary string of length 3.So starting from "000" all way up to "111"

"000"={empty set}

"001"={1} (note: Least significant bit denotes first element)

"010"={2}

"011"={1,2}

"100"={3}

"101"={1,3}

"110"= {2,3}

"111"={1,2,3}.

In implementation we can simply use integer instead of binary string and perform bitwise operation on the integer only .In the code the if condition basically checks if jth bit is set in the binary representation of integer is set or not.

 There are many bitwise operations that are analogous to set operations will be explained in next post.