python tất cả các kết hợp của tập hợp con của một chuỗi

Question

Tôi cần tất cả các kết hợp các tập hợp con của một chuỗi. Ngoài ra, một tập hợp con có độ dài 1 chỉ có thể được theo sau bởi tập hợp con có độ dài> 1. Ví dụ: cho chuỗi 4824 kết quả nên là:

[ [4, 824], [4, 82, 4], [48, 24], [482, 4], [4824] ] 

Cho đến nay tôi quản lý để lấy tất cả các tập con có thể với:

length = len(number) 
    ss = [] 
    for i in xrange(length): 
     for j in xrange(i,length): 
      ss.append(number[i:j + 1]) 

mà mang lại cho tôi:

['4', '48', '482', '4824', '8', '82', '824', '2', '24', '4'] 

Nhưng tôi không biết làm thế nào để kết hợp những người bây giờ.

Answer 1

Đầu tiên, hãy viết một hàm để tạo tất cả các phân vùng của chuỗi:

def partitions(s): 
    if s: 
     for i in range(1, len(s) + 1): 
      for p in partitions(s[i:]): 
       yield [s[:i]] + p 
    else: 
     yield [] 

lặp này tất cả các phân đoạn có thể đầu tiên (một nhân vật, hai nhân vật, vv) và kết hợp với những người có tất cả các phân vùng cho phần còn lại tương ứng của chuỗi.

>>> list(partitions("4824")) 
[['4', '8', '2', '4'], ['4', '8', '24'], ['4', '82', '4'], ['4', '824'], ['48', '2', '4'], ['48', '24'], ['482', '4'], ['4824']] 

Bây giờ, bạn chỉ có thể lọc những dữ liệu phù hợp với điều kiện của bạn, tức là những người không có hai đoạn liên tiếp có chiều dài một.

>>> [p for p in partitions("4824") if not any(len(x) == len(y) == 1 for x, y in zip(p, p[1:]))] 
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']] 

Đây là công thức chung để lặp qua tất cả các cặp mục liên tiếp.

---

Cập nhật: Thực ra, kết hợp hạn chế của bạn trực tiếp vào partition chức năng không phải là khó khăn, một trong hai. Chỉ cần theo dõi phân đoạn cuối cùng và đặt độ dài tối thiểu cho phù hợp.

def partitions(s, minLength=1): 
    if len(s) >= minLength: 
     for i in range(minLength, len(s) + 1): 
      for p in partitions(s[i:], 1 if i > 1 else 2): 
       yield [s[:i]] + p 
    elif not s: 
     yield [] 

Demo:

>>> print list(partitions("4824")) 
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']] 

Answer 2

sẽ là thú vị để xem trường hợp thử nghiệm nhiều hơn, các thuật toán sau đây làm những gì bạn nói:

s="4824" 

def partitions(s): 
    yield [s] 
    if(len(s)>2): 
    for i in range(len(s)-1, 0, -1): 
     for g in partitions(s[i:]): 
     out = [s[:i]] + g 
     if not any([len(out[i]) == len(out[i+1]) and len(out[i])==1 for i in range(len(out)-1)]): 
      yield out 

list(partitions(s)) 

bạn nhận được:

[['4824'], ['482', '4'], ['48', '24'], ['4', '824'], ['4', '82', '4']] 

giải thích

tôi dựa trên các thuật toán sau đây:

s="4824" 

def partitions_original(s): 
    #yield original string 
    yield [s] 
    if(len(s)>2): 
    for i in range(len(s)-1, 0, -1): 
     #divide string in two parts 
     #iteration 1: a="482", b="4" 
     #iteration 2: a="48", b="24" 
     #iteration 3: a="4", b="824" 
     a = s[:i] 
     b = s[i:] 
     #recursive call of b 
     for g in partitions_original(b): 
     #iteration 1: b="4", g=[['4']] 
     #iteration 2: b="24", g=[['24']] 
     #iteration 3: b="824", g=[['824'], ['82', '4'], ['8', '24']] 
     yield [a] + g 

list(partitions_original(s)) 

bạn nhận được:

[['4824'], ['482', '4'], ['48', '24'], ['4', '824'], 
['4', '82', '4'], ['4', '8', '24']] 

vấn đề là ['4', '8', '24'] ..... sau đó tôi phải thêm if mã, vì "một tập hợp con của độ dài 1 chỉ có thể được theo sau bởi tập hợp con có độ dài> 1 "

[len(out[i]) == len(out[i+1]) and len(out[i])==1 for i in range(len(out)-1)] trả lại cho ['4', '8', '24'] ->[True, False] ....any Return True nếu bất kỳ yếu tố của iterable là đúng

LƯU Ý

cũng có thể sử dụng:

if all([len(out[i]) != len(out[i+1]) or len(out[i])!=1 for i in range(len(out)-1)]):

Answer 3

Những gì tôi đang làm gì ở đây là để có được tất cả các vị trí phân chia thể của chuỗi và loại bỏ chuỗi cuối cùng. Ví dụ:

ví dụ, trong một số chuỗi có 5 số "12345", có 4 vị trí có thể tách chuỗi, gọi là possibility = (0,0,0,0),(1,0,1,0) ... với (0,0,1,0) mean (don't separate 1 and 2345,don't separate 12 and 345,separate 123 and 45,don't separate 1234 and 5) để bạn có thể nhận được tất cả các khả năng trong khi điều kiện của bạn được xác minh từ chúng tôi loại bỏ trường hợp (1,1,1,1).

import itertools 
from math import factorial 
from itertools import product 

def get_comb(string): 
    L = len(string_) 
    combinisation = [] 

    for possibility in product([0,1], repeat=len(string_)-1): 
     s = [] 
     indexes = [i for i in range(len(string_)-1) if list(possibility)[i]!=0] 
     if sum(indexes) != 0: 
      if sum(indexes) != len(string_)-1: 
       for index in indexes: 
        s.append(string_[:index+1]) 
       s.append(string_[indexes[-1:][0]+1:]) 
       combinisation.append(s) 
      else: 
       combinisation.append(string_) 
    return combinisation 



string_ = '4824' 
print "%s combinations:"%string_ 
print get_comb(string_) 



string_ = '478952' 
print "%s combinations:"%string_ 
print get_comb(string_) 



string_ = '1234' 
print "%s combinations:"%string_ 
print get_comb(string_) 


>> 
4824 combinations: 
[['482', '4'], ['48', '24'], '4824', ['4', '482', '4'], ['4', '48', '24'], '4824 
'] 
478952 combinations: 

[['47895', '2'], ['4789', '52'], ['4789', '47895', '2'], ['478', '952'], ['478', 
'47895', '2'], '478952', ['478', '4789', '47895', '2'], ['47', '8952'], '478952 
', ['47', '4789', '52'], ['47', '4789', '47895', '2'], ['47', '478', '952'], ['4 
7', '478', '47895', '2'], ['47', '478', '4789', '52'], ['47', '478', '4789', '47 
895', '2'], ['4', '47895', '2'], ['4', '4789', '52'], ['4', '4789', '47895', '2' 
], ['4', '478', '952'], ['4', '478', '47895', '2'], '478952', ['4', '478', '4789 
', '47895', '2'], ['4', '47', '8952'], '478952', ['4', '47', '4789', '52'], ['4' 
, '47', '4789', '47895', '2'], ['4', '47', '478', '952'], ['4', '47', '478', '47 
895', '2'], ['4', '47', '478', '4789', '52'], ['4', '47', '478', '4789', '47895' 
, '2']] 

1234 combinations: 

[['123', '4'], ['12', '34'], '1234', ['1', '123', '4'], ['1', '12', '34'], '1234 
'] 

Answer 4

Một mã bình thường có thể được viết như sau:

s=raw_input('enter the string:') 
word=[] 
for i in range(len(s)): 
    for j in range(i,len(s)): 
     word.append(s[i:j+1]) 

print word 
print 'no of possible combinations:',len(word) 

Và đầu ra: nhập vào chuỗi: [ '4', '48', '482', '4824', '8', '82', '824', '2', '24', '4'] không có kết hợp nào có thể: 10