Podziel ciąg na wszystkie możliwe uporządkowane frazy.

Question

Próbuję zbadać funkcjonalność wbudowanych funkcji Pythona. Obecnie próbuję pracować aż coś pobiera ciąg, takich jak:

'the fast dog' 

i przerwać ciąg w dół do wszystkich możliwych zamówionych zwrotów, jak list. W powyższym przykładzie byłoby wyjście jak:

[['the', 'fast dog'], ['the fast', 'dog'], ['the', 'fast', 'dog']] 

Kluczową rzeczą jest to, że oryginalna kolejność słów w ciągu musi być zachowana podczas generowania ewentualnych zwrotów.

Udało mi się uzyskać funkcję do pracy, która może to zrobić, ale jest dość uciążliwa i brzydka. Jednak zastanawiałem się, czy niektóre z wbudowanych funkcji w Pythonie mogą być użyteczne. Myślałem, że może być możliwe podzielenie ciągu na różne białe przestrzenie, a następnie zastosować je rekursywnie do każdego podziału. Czy ktokolwiek może mieć jakieś sugestie?

Answer 1

Korzystanie itertools.combinations:

import itertools 

def break_down(text): 
    words = text.split() 
    ns = range(1, len(words)) # n = 1..(n-1) 
    for n in ns: # split into 2, 3, 4, ..., n parts. 
     for idxs in itertools.combinations(ns, n): 
      yield [' '.join(words[i:j]) for i, j in zip((0,) + idxs, idxs + (None,))] 

Przykład:

>>> for x in break_down('the fast dog'): 
...  print(x) 
... 
['the', 'fast dog'] 
['the fast', 'dog'] 
['the', 'fast', 'dog'] 

>>> for x in break_down('the really fast dog'): 
...  print(x) 
... 
['the', 'really fast dog'] 
['the really', 'fast dog'] 
['the really fast', 'dog'] 
['the', 'really', 'fast dog'] 
['the', 'really fast', 'dog'] 
['the really', 'fast', 'dog'] 
['the', 'really', 'fast', 'dog'] 

Answer 2

Pomyśl o zestawie odstępów między słowami. Każdy podzbiór tego zbioru odpowiada zestaw dzielonych punktów i ostatecznie do rozłamu w zdaniu:

the fast dog jumps 
    ^1 ^2 ^3  - these are split points 

Na przykład podzbiór {1,3} odpowiada rozłamu {"the", "fast dog", "jumps"}

podzbiory mogą być wyliczone jako liczb binarnych od 1 do 2^(l-1) -1 gdzie L oznacza liczbę słów

001 -> the fast dog, jumps 
010 -> the fast, dog jumps 
011 -> the fast, dog, jumps 
etc. 

Answer 3

operacja zażądać jest zazwyczaj nazywany „przegroda”, a to może być zrobione w dowolnym rodzaju listy. Tak, niech wdrożyć partycjonowanie każdej listy:

def partition(lst): 
    for i in xrange(1, len(lst)): 
     for r in partition(lst[i:]): 
      yield [lst[:i]] + r 
    yield [lst] 

Zauważ, że tam będzie wiele przegródek na dłuższych listach, więc zaleca się wdrożyć go jako generator. Aby sprawdzić, czy to działa, spróbuj:

print list(partition([1, 2, 3])) 

Teraz chcesz podzielić ciąg znaków za pomocą słów jako elementów. Najprostszym sposobem, aby zrobić tę operację jest podzielony tekst słowami, uruchom oryginalny algorytm partycjonowania i scalania grupy wyrazów z powrotem do strun:

def word_partition(text): 
    for p in partition(text.split()): 
     yield [' '.join(group) for group in p] 

Ponownie, aby go przetestować, zastosowanie:

print list(word_partition('the fast dog')) 

Answer 4

Opracuję nieco rozwiązania @ grep, używając tylko wbudowanych, jak podano w pytaniu i unikając rekursji. Możliwe, że w jakikolwiek sposób zrealizujesz swoją odpowiedź:

#! /usr/bin/python3 

def partition (phrase): 
    words = phrase.split() #split your phrase into words 
    gaps = len (words) - 1 #one gap less than words (fencepost problem) 
    for i in range (1 << gaps): #the 2^n possible partitions 
     r = words [:1] #The result starts with the first word 
     for word in words [1:]: 
      if i & 1: r.append (word) #If "1" split at the gap 
      else: r [-1] += ' ' + word #If "0", don't split at the gap 
      i >>= 1 #Next 0 or 1 indicating split or don't split 
     yield r #cough up r 

for part in partition ('The really fast dog.'): 
    print (part)