Teilen Sie eine Zeichenfolge in alle möglichen geordneten Phrasen

Question

Ich versuche, die Funktionalität der integrierten Funktionen von Python zu erkunden. Ich versuche zur Zeit etwas aufzuarbeiten, die eine Zeichenfolge wie nimmt:

'the fast dog' 

und bricht die Saite nach unten in alle möglichen geordneten Sätze, als Listen. Das obige Beispiel würde die Ausgabe wie folgt zusammen:

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

Das Wichtigste ist, dass die ursprüngliche Reihenfolge der Wörter in der Kette erhalten werden muss, wenn die möglichen Phrasen zu erzeugen.

Ich konnte eine funktion zu arbeiten, die dies tun kann, aber es ist ziemlich umständlich und hässlich. Ich habe mich jedoch gefragt, ob einige der eingebauten Funktionen in Python nützlich sein könnten. Ich dachte, dass es möglich sein könnte, die Zeichenfolge in verschiedene weiße Leerzeichen aufzuteilen, und dies dann rekursiv auf jeden Teilbereich anzuwenden. Könnte jemand Vorschläge haben?

Answer 1

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

Beispiel:

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

Denken des Satzes von Lücken zwischen den Wörtern. Jede Teilmenge dieser Menge entspricht einen Satz von Splitpunkten und schließlich zur Spaltung des Satzes:

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

Zum Beispiel ist die Teilmenge {1,3} entspricht die geteilten {"the", "fast dog", "jumps"}

Subsets können als binäre Zahlen aufgezählt werden von 1 bis 2^(L-1) -1, wobei L Anzahl der Worte

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

Answer 3

der Vorgang, den Sie verlangen in der Regel eine „Partition“, und es kann über jede Art von Liste aufgerufen wird, durchgeführt werden. So lassen Sie sich Partitionierung jeder Liste implementieren:

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

Hinweis, dass es viele Partitionen für längere Listen sein, so ist es bevorzugt, sie als Generator zu implementieren. Um zu überprüfen, ob es funktioniert, versuchen Sie:

Jetzt möchten Sie eine Zeichenfolge mit Worten als Elemente partitionieren. Der einfachste Weg, um diesen Vorgang zu tun ist, Text zur Trennung von Worten, den ursprünglichen Partitionierungsalgorithmus ausführen, und verschmelzen Gruppen von Worten zurück in Strings:

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

Wieder zu testen, verwenden Sie:

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

Answer 4

Ich werde ein wenig auf die Lösung von @ grep eingehen, während ich nur die in der Frage angegebenen Einfügungen verwende und Rekursionen vermeide. Sie könnten möglicherweise seine Antwort irgendwie in diese Richtung implementieren:

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