Все способы сегментировать строку

Question

Я пытаюсь найти эффективный алгоритм, чтобы получить все способы разбить строку,

, например, для данной строки «ABCD» =>
«а» «BCD»
'а' 'B' 'CD'
'а' 'B' 'с' 'd'
'аb' 'CD'
'аb' 'с' 'd'
'ABC' 'd'
'a', 'bc', 'd

любой язык wo uld Оценить

Заранее благодарен!

Answer 1

Анализ проблемы

Между каждой парой соседних символов, вы можете решить, нужно ли вырезать. Для строки размера n есть n-1 позиций, где вы можете вырезать или нет, т. Е. Есть две возможности. Поэтому есть 2^(n-1) разделов для каждой строки размера n.

Благодаря размеру только на выходе (2^(n-1) разделов, каждый из которых состоит из n символов из строки +) сепаратора обеспечивает, алгоритм для решения этой проблемы может иметь экспоненциальное время работы в лучшем случае (2^(n-1) * n → O(2^n)).

---

Решение

Я решил представлять раздел как целое. Каждый бит в cutpoints определяет, следует ли разрезать между символами i и i+1. Чтобы перебирать все возможные разделы, нам просто нужно пройти через все целые числа между 0 и 2^(n-1) - 1.

Пример: Для строки длины 4, мы проходим через все целые числа между 0 и 2^3 - 1 или 0 и 7 или в двоичной системе: 000 и 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) 

Использование памяти:

Я думаю, что мое решение использует O(n) память с Python 3. Только один раздел создан в то время, это напечатано, а не ссылаться больше. Это, конечно, меняется, если вы сохраняете все результаты, например. путем их хранения в списке.

В Python 2 заменить range с xrange, в противном случае все возможные cutpoints будут сохранены в списке, поэтому необходимости экспоненциальный объем памяти.

---

решение JavaScript

// 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); 
} 

Испытано с NodeJS v4.4.3 (оговорке: Я не использовал NodeJS раньше).

Answer 2

Это решение, которое минимизирует время разработчика, используя встроенный итератор. Это должно быть достаточно быстро для проблемных размеров, для которых сам ответ не является чрезмерно большим.

Существует взаимно однозначное соответствие между разделами строки и подмножествами потенциальных точек пересечения. Если длина строки n, то есть n-1 мест, где вы можете отрезать строку. Прямым способом было бы итерации через такие подмножества, и для каждого такого подмножества срезайте строку таким образом. Вот подход Python, который использует стандартные модули itertools:

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) 

Например:

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

Следует отметить, что этот подход производит генерирует ['World'] в качестве раздела 'World'. Это соответствует разрезанию с пустым набором точек разреза. Я рассматриваю это как функцию, а не ошибку, поскольку стандартное математическое определение раздела позволяет разбивать набор на одну часть. Если это нежелательно для ваших целей, исправление достаточно просто - просто перебирайте непустые подмножества точек разреза. С точки зрения приведенного выше кода, это исправление сводится к добавлению двух символов в allPartitions: заменить

for k in range(n): 

по

for k in range(1,n): 

Answer 3

Что-то вдоль линий следующего (образец тестировался и, вероятно, багги VB.NET)

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 

в основном это работает, говоря, что мы можем взять «ABCD» и разделить его на

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

затем вычислить 'BCD', мы просто повторяем процесс, как описано выше, только с

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

и т.д. повторяется рекурсивно.

Однако этот код не особенно эффективен во время выполнения. Одна вещь, которую вы могли бы сделать, чтобы значительно ускорить ее, - добавить словарь (Of String, List (Of List (Of String)) вне функции, в которой вы можете хранить кеш результатов, и если элемент существует там , вы возвращаетесь оттуда, если нет, вычисляете его и добавляете. Списки также могут быть не самыми эффективными, а функция ToList может быть не самым быстрым способом клонирования.Тем не менее, я упростил его, чтобы было легче понять, а также сэкономить время на его разработку!

Answer 4

GeeksforGeeks обеспечил хорошо объяснено решением этой проблемы:

Для строки abcd будет 2^(N-1), то есть 8 разделов.

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

Суть решения заключается в recursion печатать все перестановки.
поддерживают два параметра - индекс следующего обрабатываемого символа и выходную строку до сих пор.Мы начинаем с индекса следующего обрабатываемого символа, добавляем подстроку, образованную необработанной строкой, к выходной строке и возвращаем оставшуюся строку до тех пор, пока мы не обработаем всю строку.

// 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, ""); 
    } 
} 

Время Сложность O (2^п)

Вот ссылка на статью: http://www.geeksforgeeks.org/print-ways-break-string-bracket-form/