Finding Subsequences of a large String

Question

I am trying to get all the Subsequences of a String. Example:-

firstString = "ABCD"

O/P should be;

'ABCD', 'BCD', 'ACD', 'ABD', 'ABC', 'CD', 'BD', 'BC', 'AD', 'AC', 'AB', 'D', 'C', 'B', 'A'

For that I am using following part of code:-

#!usr/bin/python

from __future__ import print_function
from operator import itemgetter
from subprocess import call
import math
import itertools
import operator

call(["date"])

firstArray = []

firstString = "ABCD"

firstList = list(firstString)

for L in range(0, len(firstList)+1):
    for subset in itertools.combinations(firstList, L):

            firstArray.append(''.join(subset))

firstArray.reverse()

print (firstArray)

call(["date"])

But this code is not scalable.

If I provide :-

firstString = "ABCDABCDABCDABCDABCDABCDABCD"

The program takes almost 6 mins time to complete.

---------------- Capture while running the script --------------------

python sample-0012.py
Wed Feb  8 21:30:30 PST 2017
Wed Feb  8 21:30:30 PST 2017

Can someone please help?

I think you have to be realistic. The string is 28 characters long, which gives a powerset of length 268435456 (ok one less if you don't include the empty set). It's never going to be happening in the blink of an eye. Calling reverse certainly doesnt help, as it precludes using a lazy iterator. Perhaps if you really want lowest first perhaps you could use `combinations(data, len(firstList) - r) ` to retrieve larger combinations first. — Paul Rooney, Feb 09 '17 at 22:18

score 0 · Answer 1 · edited May 23 '17 at 10:29

0

What you are looking for is called a "Power set" (or Powerset). The wikipedia def:

a power set (or powerset) of any set S is the set of all subsets of S, including the empty set and S itself.

A good solution might be recursive, here you can find one: link

edited May 23 '17 at 10:29

Community

1
1

answered Feb 09 '17 at 06:33

J63

833
1
8
22

score 0 · Answer 2 · edited May 23 '17 at 12:26

For better doing with powerset concept go through, How to get all possible combinations of a list’s elements?

 otherwise, you can do like this. 
    wordlist = []    
    for i in range(len(firststring)):
            ...:     comblist = combinations(list(firststring), i+1)
            ...:     same_length_words = []
            ...:     for i, word in enumerate(comblist):
            ...:         if word not in same_length_words:
            ...:             same_length_words.append(word)
            ...:     for each_word in same_length_words:
            ...:         wordlist.append(''.join(each_word))
            ...:

score 0 · Answer 3 · answered Feb 09 '17 at 07:48

try this

from itertools import chain, combinations
firstString = 'ABCD'
data = list(firstString)
lists =  chain.from_iterable(combinations(data, r) for r in range(len(data)+1))
print [''.join(i) for i in lists if i]

# ['A', 'B', 'C', 'D', 'AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'ACD', 'BCD', 'ABCD']

Finding Subsequences of a large String

3 Answers3