python wszystkie kombinacje podzbiorów ciągu znaków

Question

Potrzebuję wszystkich kombinacji podzbiorów ciągu. Dodatkowo, podzbiór o długości 1 może być śledzony tylko przez podzbiór o długości> 1. E.g. dla łańcucha 4824 wynik powinien być:

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

Do tej pory udało mi się odzyskać wszystkie możliwe podzbiory z:

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

który daje mi:

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

Ale nie wiem jak je teraz łączyć.

Answer 1

Najpierw napisać funkcję do generowania wszystkie rozbiorach napisu:

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

tej iteruje wszystkie możliwe pierwsze segmenty (jeden znak, dwa znaki, etc.) i łączy te z całą partycje dla odpowiedniej reszty ciągu.

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

Teraz można filtrować tylko te, które pasują do warunków, to znaczy takie, które nie mają dwa kolejne podciągi o długości jeden.

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

Tutaj zip(p, p[1:]) jest częstym przepis na Iterowanie nad wszystkie pary kolejnych elementów.

---

Aktualizacja: Faktycznie, zawierające wiązanie bezpośrednio do funkcji partition nie jest trudne, albo. Po prostu śledź ostatni segment i ustaw odpowiednio minimalną długość.

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

byłoby ciekawe zobaczyć więcej przypadków testowych, następujący algorytm robi to, co mówisz:

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)) 

otrzymasz:

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

wyjaśnienie

I na podstawie następującego algorytmu:

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)) 

otrzymasz:

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

problem jest ['4', '8', '24'] ..... to muszę dodać if do kodu, ponieważ „a podzbiór o długości 1 może śledzić tylko podzbiór o długości> 1 "

[len(out[i]) == len(out[i+1]) and len(out[i])==1 for i in range(len(out)-1)] return for ['4', '8', '24'] ->[True, False] ....any Zwraca True jeżeli każdy element iterowalny prawda

UWAGA

również może być używany:

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

Answer 3

Co robię tutaj jest, aby wszystkie możliwe podziału pozycję ciągu i wyeliminować ostatni.

na przykład, w niektórych ciągach z 5 cyframi "12345" dla przykładu, istnieje 4 możliwe położenie, aby podzielić ciąg, nazwij go possibility = (0,0,0,0),(1,0,1,0) ... z (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), dzięki czemu możesz uzyskać wszystkie możliwości, gdy twój stan jest zweryfikowany od eliminujemy przypadek (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

Zwykły kod może być napisany tak:

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) 

i wyjście: wprowadzić ciąg: [ '4', '48', '482', '4824', "8", "82", "824", "2", "24", "4"] liczba możliwych kombinacji: 10