Alle Möglichkeiten, um eine Zeichenfolge zu partitionieren

Question

Ich versuche, einen effizienten Algorithmus zu finden alle Möglichkeiten, um eine Zeichenfolge

zB für eine bestimmte Zeichenfolge ‚abcd‘ =>
‚a‘ ‚bcd‘ zu partitionieren
'a' 'B' 'cd'
'a' 'b' 'c' 'd'
'ab' 'cd'
'ab' 'c' 'd'
'abc' 'd'
'a', 'bc', 'd

jede Sprache wo old be geschätzt

Vielen Dank im Voraus!

Answer 1

Problemanalyse

Zwischen jedem Paar von benachbarten Zeichen, können Sie entscheiden, ob zu schneiden. Für eine Zeichenfolge der Größe n gibt es n-1 Positionen, wo Sie schneiden können oder nicht, d. H. Es gibt zwei Möglichkeiten. Daher gibt es 2^(n-1) Partitionen für jede Zeichenfolge der Größe n.

Aufgrund der Größe des Ausgangs allein (2^(n-1) Partitionen, die jeweils aus n Zeichen aus der Zeichenfolge + seperators), um einen Algorithmus zu lösen diese exponentielle Laufzeit bestenfalls haben kann (2^(n-1) * n → O(2^n)).

---

Lösung

Ich wählte eine Partition als ganze Zahl darzustellen. Jedes Bit in cutpoints bestimmt, ob zwischen den Zeichen i und i+1 abgeschnitten werden soll. Um alle möglichen Partitionen zu durchlaufen, müssen wir einfach alle Ganzzahlen zwischen 0 und 2^(n-1) - 1 durchlaufen.

Beispiel: Für eine Zeichenfolge der Länge 4, gehen wir durch alle ganzen Zahlen zwischen 0 und 2^3 - 1 oder 0 und 7 oder in binär: 000 und 111.

# (python 2 or 3) 
def all_partitions(string): 
    for cutpoints in range(1 << (len(string)-1)): 
     result = [] 
     lastcut = 0 
     for i in range(len(string)-1): 
      if (1<<i) & cutpoints != 0: 
       result.append(string[lastcut:(i+1)]) 
       lastcut = i+1 
     result.append(string[lastcut:]) 
     yield result 

for partition in all_partitions("abcd"): 
    print(partition) 

Speichernutzung:

Ich glaube, meine Lösung verwendet O(n) Speicher mit Python 3. Nur eine Partition zu einem Zeitpunkt erzeugt wird, wird es gedruckt und nicht mehr verwiesen wird. Dies ändert sich natürlich, wenn Sie alle Ergebnisse, z. indem Sie sie in einer Liste speichern.

Ersetzen Sie in Python 2 range durch xrange, sonst werden alle möglichen cutpoints in einer Liste gespeichert und benötigen daher eine exponentielle Speichermenge.

---

JavaScript-Lösung

// ES6 generator 
function* all_partitions(string) { 
    for (var cutpoints = 0; cutpoints < (1 << (string.length - 1)); cutpoints++) { 
     var result = []; 
     var lastcut = 0; 
     for (var i = 0; i < string.length - 1; i++) { 
      if (((1 << i) & cutpoints) !== 0) { 
       result.push(string.slice(lastcut, i + 1)); 
       lastcut = i + 1; 
      } 
     } 
     result.push(string.slice(lastcut)); 
     yield result; 
    } 
} 

for (var partition of all_partitions("abcd")) { 
    console.log(partition); 
} 

Getestet mit NodeJS v4.4.3 (Disclaimer: Ich habe nicht NodeJS verwendet vor).

Answer 2

Dies ist eine Lösung, die Entwicklerzeit durch Nutzung eines integrierten Iterators minimiert. Bei Problemgrößen, für die die Antwort selbst nicht zu groß ist, sollte es relativ schnell gehen.

Es gibt eine Eins-zu-eins-Entsprechung zwischen Partitionen einer Zeichenfolge und Teilmengen von potenziellen Schnittpunkten. Wenn die Länge der Zeichenfolge n ist, gibt es n-1 Orte, an denen Sie die Zeichenfolge schneiden könnten. Ein direkter Weg wäre, solche Teilmengen zu durchlaufen und für jede Teilmenge die Kette auf diese Weise zu zerlegen. Hier ist ein Python-Ansatz, der die Standardmodule itertools verwendet:

import itertools 

def multiSlice(s,cutpoints): 
    k = len(cutpoints) 
    if k == 0: 
     return [s] 
    else: 
     multislices = [s[:cutpoints[0]]] 
     multislices.extend(s[cutpoints[i]:cutpoints[i+1]] for i in range(k-1)) 
     multislices.append(s[cutpoints[k-1]:]) 
     return multislices 

def allPartitions(s): 
    n = len(s) 
    cuts = list(range(1,n)) 
    for k in range(n): 
     for cutpoints in itertools.combinations(cuts,k): 
      yield multiSlice(s,cutpoints) 

Zum Beispiel:

>>> parts = allPartitions('World') 
>>> for p in parts: print(p) 

['World'] 
['W', 'orld'] 
['Wo', 'rld'] 
['Wor', 'ld'] 
['Worl', 'd'] 
['W', 'o', 'rld'] 
['W', 'or', 'ld'] 
['W', 'orl', 'd'] 
['Wo', 'r', 'ld'] 
['Wo', 'rl', 'd'] 
['Wor', 'l', 'd'] 
['W', 'o', 'r', 'ld'] 
['W', 'o', 'rl', 'd'] 
['W', 'or', 'l', 'd'] 
['Wo', 'r', 'l', 'd'] 
['W', 'o', 'r', 'l', 'd'] 

Beachten Sie, dass dieser Ansatz erzeugt erzeugt ['World'] als Trennwand von 'World'. Dies entspricht dem Schneiden mit einem leeren Satz von Schnittpunkten. Ich betrachte das eher als ein Feature als als einen Fehler, da die standardmäßige mathematische Definition von Partition die Partitionierung eines Sets in ein Stück ermöglicht. Wenn dies für Ihre Zwecke unerwünscht ist, ist die Behebung einfach - einfach über die nicht leeren Teilmengen der Schnittpunkte iterieren. In Bezug auf die oben genannten Code, dieses Update beläuft sich auf das Hinzufügen von zwei Zeichen zu allPartitions:

for k in range(n): 

von

for k in range(1,n): 

Answer 3

Etwas nach dem Vorbild der folgenden (ungetestet und wahrscheinlich Buggy VB.NET Probe) ersetzen

Function FindAllGroups(s As String) As List(Of List(Of String)) 
    Dim ret As New List(Of List(Of String)) 
    Dim l As New List(Of String) 
    l.Add(s) 'the whole string unbroken 
    ret.Add(l) 'first option we return is the whole unbroken string by itself 
    If s.Length > 1 Then 
     Dim tmp = FindAllGroups(s.Substring(1)) 'find all the groups for the rest of the string after the first character 
     For Each l2 in tmp 
      l = l2.ToList 'Copy it 
      l.Insert(s.SubString(0,1),0)'insert the first character from this string by itself before this combination for the rest of the string 
      ret.Add(l) 
     Next 
     For Each l2 in tmp 
      l = l2.ToList 'Copy it 
      l(0)= s.SubString(0,1) & l(0) 'insert the first character from this string as part of the first element in the list 
      ret.Add(l) 
     Next 
    End If 
    Return ret 
End Function 

Diese im Grunde funktioniert sagen, dass wir ‚abcd‘ nehmen und spaltete es in

'a', 1st option for 'bcd' split 
'a', 2nd option for 'bcd' split 
... 
+ 
1st option for 'bcd' split with the first element prepended with 'a' 
2nd option for 'bcd' split with the first element prepended with 'a' 
... 

dann 'bcd' zu berechnen, wir wiederholen Sie den Vorgang wie oben, nur mit

'b', 1st option for 'cd' split 
'b', 2nd option for 'cd' split 
... 
+ 
1st option for 'cd' split with the first element prepended with 'b' 
2nd option for 'cd' split with the first element prepended with 'b' 
... 

usw. rekursiv wiederholt.

Dieser Code ist jedoch zur Laufzeit nicht besonders effizient. Eine Sache, die Sie tun könnten, um es erheblich zu beschleunigen, wäre, ein Dictionary (Of String, List (Of List) außerhalb der Funktion hinzuzufügen, in dem Sie einen Cache der Ergebnisse speichern können und ob das Element dort existiert) , Sie kommen von dort zurück, wenn nicht, berechnen Sie es und fügen Sie es hinzu Listen sind auch möglicherweise nicht die effizienteste, und die ToList-Funktion ist möglicherweise nicht die schnellste Art zu klonen.Ich habe es jedoch vereinfacht, um es einfacher zu verstehen und mir auch Zeit zu sparen, es zu verarbeiten!

Answer 4

GeeksforGeeks hat eine gut erklärt Lösung für dieses Problem zu finden:

Bei String abcd wird es 2^(n-1), das heißt 8 Partitionen sein.

(a)(b)(c)(d) 
(a)(b)(cd) 
(a)(bc)(d) 
(a)(bcd) 
(ab)(c)(d) 
(ab)(cd) 
(abc)(d) 
(abcd) 

Der Kern der Lösung liegt in der recursion alle Permutationen zu drucken.
pflegen Sie zwei Parameter - Index des nächsten zu verarbeitenden Zeichens und der Ausgabe-String so weit.Wir beginnen mit dem Index des nächsten Zeichens, das verarbeitet werden soll, fügen die Teilzeichenfolge, die von der nicht verarbeiteten Zeichenkette gebildet wird, an die Ausgabezeichenfolge an und rekursieren die verbleibende Zeichenkette, bis wir die gesamte Zeichenkette verarbeitet haben.

// Java program to find all combinations of Non- 
// overlapping substrings formed from given 
// string 

class GFG 
{ 
    // find all combinations of non-overlapping 
    // substrings formed by input string str 
    static void findCombinations(String str, int index, 
           String out) 
    { 
     if (index == str.length()) 
      System.out.println(out); 

     for (int i = index; i < str.length(); i++) 

      // append substring formed by str[index, 
      // i] to output string 
      findCombinations(str, i + 1, out + 
       "(" + str.substring(index, i+1) + ")"); 
    } 

    // driver program 
    public static void main (String[] args) 
    { 
     // input string 
     String str = "abcd"; 
     findCombinations(str, 0, ""); 
    } 
} 

Zeitkomplexität O (2^n)

Hier ist der Link zum Artikel: http://www.geeksforgeeks.org/print-ways-break-string-bracket-form/