Đường con của chuỗi bằng cách sử dụng Python

Question

Có bao nhiêu substrings bạn có thể tạo ra một chuỗi như abcd không?

Làm thế nào tôi có thể nhận được tất cả các chuỗi con của nó:

['a', 'b', 'c', 'd', 'ab', 'bc', 'cd', 'abc', 'bcd', 'abcd'] 

Answer 1

Hãy thử điều này:

def consecutive_groups(iterable): 
    s = tuple(iterable) 
    for size in range(1, len(s)+1): 
     for index in range(len(s)+1-size): 
      yield iterable[index:index+size] 

>>> print list(consecutive_groups('abcd')) 
['a', 'b', 'c', 'd', 'ab', 'bc', 'cd', 'abc', 'bcd', 'abcd'] 

Và số kết hợp chỉ đơn giản là bằng tổng từ 1 tới độ dài của chuỗi, tương đương với n * (n + 1)/2.

Bằng cách này, nếu bạn muốn tránh trùng lặp, bạn chỉ có thể sử dụng một địa phương xác định thiết lập trong chức năng máy phát điện, như vậy:

def consecutive_groups(iterable): 
    s = tuple(iterable) 
    seen = set() 
    for size in range(1, len(s)+1): 
     for index in range(len(s)+1-size): 
      slc = iterable[index:index+size] 
      if slc not in seen: 
       seen.add(slc) 
       yield slc 

đang Đó là một chút khó sử dụng hơn và có lẽ có thể là được tối ưu hóa cho thụt đầu dòng, nhưng nó sẽ làm cho một bằng chứng về khái niệm.

Answer 2

Đây là những gì bạn muốn:

In [260]: S = 'abcd' 

In [261]: list(itertools.chain.from_iterable([list(itertools.combinations(S,i)) for i in range(1,len(S))])) 
Out[261]: 
[('a',), 
('b',), 
('c',), 
('d',), 
('a', 'b'), 
('a', 'c'), 
('a', 'd'), 
('b', 'c'), 
('b', 'd'), 
('c', 'd'), 
('a', 'b', 'c'), 
('a', 'b', 'd'), 
('a', 'c', 'd'), 
('b', 'c', 'd')] 

Hoặc nếu bạn thực sự muốn tất cả chúng như dây đàn, bạn có thể làm:

In [262]: combos = list(itertools.chain.from_iterable([list(itertools.combinations(S,i)) for i in range(1,len(S))])) 

In [263]: [''.join(c) for c in combos] 
Out[263]: 
['a', 
'b', 
'c', 
'd', 
'ab', 
'ac', 
'ad', 
'bc', 
'bd', 
'cd', 
'abc', 
'abd', 
'acd', 
'bcd'] 

EDIT Để có được chỉ chuỗi con của S:

In [270]: list(itertools.chain.from_iterable([[S[i:i+k] for i in range(len(S)-k)] for k in range(1,len(S)+1)])) + [S] 
Out[270]: ['a', 'b', 'c', 'ab', 'bc', 'abc', 'abcd'] 

Answer 3

Có hai câu hỏi ở đó .

Đầu tiên, How many substrings can you make out of a string like “abcd”? là một sự kết hợp như thế này:

import itertools 
s='abcd' 
com=[list(itertools.combinations(s,x)) for x in range(1,len(s)+1)] 

print [''.join(e) for e in sum(com,[])] 

in:

['a', 'b', 'c', 'd', 'ab', 'ac', 'ad', 'bc', 'bd', 'cd', 'abc', 'abd', 'acd', 'bcd', 'abcd'] 

Câu hỏi thứ hai là làm thế nào để tái tạo ví dụ của bạn (mà không phải là một 'kết hợp'). Bạn có thể làm điều đó với mã này:

>>> [s[i:i+j] for j in range(1,len(s)+1) for i in range(len(s)-j+1)] 
['a', 'b', 'c', 'd', 'ab', 'bc', 'cd', 'abc', 'bcd', 'abcd'] 

Answer 4

Tôi nghĩ việc này quá và trong khi không phải là hiệu quả nhất, nó có hấp dẫn của việc sử dụng các tính năng ít phức tạp.

S = "abcd" 
substrings = [S[i:j] for i in range(len(S)) for j in range(i+1,len(S)+1)] 
substrings.sort(key=len) 

Lưu ý rằng cách tiếp cận này không loại bỏ các chất nền giống hệt nhau có thể xuất hiện. Ví dụ: nếu chuỗi con ban đầu là "abcdab", a, b và ab sẽ xuất hiện hai lần.

Answer 5

Điều này có làm được không?

import itertools 
def substrings(x): 
    for i, j in itertools.combinations(xrange(len(x)+1), 2): 
     yield x[i:j] 

hoặc là biểu hiện phát:

(x[i:j] for i, j in itertools.combinations(xrange(len(x)+1), 2)) 

Kết quả mở rộng ví dụ của bạn trông như thế này:

['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'] 

Để đặt theo chiều dài, sử dụng loại key=len.