Suddividere una stringa in tutte le frasi ordinate possibili

Question

Sto cercando di esplorare la funzionalità delle funzioni incorporate di Python. Attualmente sto cercando di lavorare a qualcosa che prende una stringa come:

'the fast dog' 

e rompere la corda verso il basso in tutte le possibili frasi ordinate, come liste. L'esempio precedente uscita sarebbe come segue:

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

La cosa fondamentale è che l'ordine originario delle parole nella stringa deve essere conservato durante la generazione delle frasi possibili.

Sono stato in grado di ottenere una funzione di lavoro che può fare questo, ma è piuttosto ingombrante e brutto. Tuttavia, mi chiedevo se alcune delle funzionalità incorporate in Python potrebbero essere utili. Stavo pensando che potrebbe essere possibile dividere la stringa in vari spazi bianchi e applicarla in modo ricorsivo a ciascuna divisione. Qualcuno potrebbe avere qualche suggerimento?

Answer 1

Utilizzando 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,))] 

Esempio:

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

Pensate l'insieme di spazi tra le parole. Ogni sottoinsieme di questo gruppo corrisponde ad un insieme di punti di divisione e infine alla scissione della frase:

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

Ad esempio, il sottoinsieme {1,3} corrisponde alla scissione {"the", "fast dog", "jumps"}

sottoinsiemi possono essere elencate come numeri binari 1-2^(L-1) -1 dove L è il numero di parole

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

Answer 3

L'operazione si richiede è di solito chiamato un “partizione”, e può essere fatto su qualsiasi tipo di lista. Quindi, cerchiamo di implementare il partizionamento di qualsiasi elenco:

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

Nota che ci saranno un sacco di partizioni per gli elenchi più lunghi, quindi è preferibile per la sua attuazione come generatore. Per verificare se funziona, provare:

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

Ora, si desidera partizionare una stringa utilizzando le parole come elementi. Il modo più semplice per farlo operazione è quello di dividere il testo con le parole, eseguire l'algoritmo di partizionamento originale, e unire gruppi di parole di nuovo in stringhe:

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

Anche in questo caso, per provarlo, uso:

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

Answer 4

Elaborerò un po 'sulla soluzione di @ grep, mentre uso solo i built-in come hai detto nella tua domanda ed evitando la ricorsione. Si potrebbe implementare la sua risposta in qualche modo in queste righe:

#! /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)