查找大字符串的子序列

我想要獲取字符串的所有子序列。例如： -查找大字符串的子序列

firstString = "ABCD"

O/P應該是;

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

對於我使用下面的代碼部分： -

#!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"])

但這種代碼是不可擴展的。

如果我提供： -

firstString = "ABCDABCDABCDABCDABCDABCDABCD"

程序需要近6分鐘的時間內完成。

----------------捕獲，同時運行該腳本--------------------

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

有人可以幫忙嗎？

來源

2017-02-09 Manas Pal

我認爲你必須現實。該字符串的長度爲28個字符，它提供了一個長度爲268435456的powerset（如果不包含空集，那麼可以少一個）。它永遠不會在眨眼之間發生。調用反向無疑無助，因爲它排除了使用懶惰的迭代器。也許如果你真的想要最低優先，也許你可以使用'組合（data，len（firstList） - r）'來首先檢索更大的組合。 –

你在找什麼叫做「Power set」（或Powerset）。維基百科DEF：

任何集合S的功率設定（或冪）是集合S，的所有子集包括空集和S本身的。

一個很好的解決方案可能是遞歸的，在這裏你可以找到一個： link

來源

2017-02-09 06:33:14 J63

爲了更好地與冪的概念做經歷， 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)) 
      ...:

來源

2017-02-09 06:40:16

試試這個

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']

來源

2017-02-09 07:48:49 Arun

查找大字符串的子序列

回答

相關問題