Print all subsequences of a string | Iterative Method | Python3 program to print all Subsequences of a string in an iterative manner ; function to find subsequence ; loop while binary is greater than ; get the position of rightmost set bit ; append at beginning as we are going from LSB to MSB ; resets bit at pos in binary ; function to print all subsequences ; map to store subsequence lexicographically by length ; Total number of non - empty subsequence in string is 2 ^ len - 1 ; i = 0 , corresponds to empty subsequence ; subsequence for binary pattern i ; storing sub in map ; it . first is length of Subsequence it . second is set < string > ; ii is iterator of type set < string > ; Driver Code
from math import log2 , floor NEW_LINE def subsequence ( s , binary ) : NEW_LINE INDENT sub = " " NEW_LINE while ( binary > 0 ) : NEW_LINE INDENT pos = floor ( log2 ( binary & - binary ) + 1 ) NEW_LINE sub = s [ pos - 1 ] + sub NEW_LINE binary = ( binary & ~ ( 1 << ( pos - 1 ) ) ) NEW_LINE DEDENT sub = sub [ : : - 1 ] NEW_LINE return sub NEW_LINE DEDENT def possibleSubsequences ( s ) : NEW_LINE INDENT sorted_subsequence = { } NEW_LINE length = len ( s ) NEW_LINE limit = 2 ** length NEW_LINE for i in range ( 1 , limit ) : NEW_LINE INDENT sub = subsequence ( s , i ) NEW_LINE if len ( sub ) in sorted_subsequence . keys ( ) : NEW_LINE INDENT sorted_subsequence [ len ( sub ) ] = tuple ( list ( sorted_subsequence [ len ( sub ) ] ) + [ sub ] ) NEW_LINE DEDENT else : NEW_LINE INDENT sorted_subsequence [ len ( sub ) ] = [ sub ] NEW_LINE DEDENT DEDENT for it in sorted_subsequence : NEW_LINE INDENT print ( " Subsequences ▁ of ▁ length ▁ = " , it , " are : " ) NEW_LINE for ii in sorted ( set ( sorted_subsequence [ it ] ) ) : NEW_LINE INDENT print ( ii , end = ' ▁ ' ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT s = " aabc " NEW_LINE possibleSubsequences ( s ) NEW_LINE