Сочетания строк при сохранении порядка слов - PullRequest
Новая
       5

Сочетания строк при сохранении порядка слов

1 голос
/ 21 января 2012

С учетом строки: 

String words = "Mary had a little lamb";

как получить комбинацию фрагментов предложения при сохранении порядка появления слов в исходном предложении ???

пример: 

{'Mary had a little lamb'}
{'Mary had a little', 'lamb'}
{'Mary had a', 'little lamb'}, {'Mary had a', 'little', 'lamb'}
{'Mary had', 'a little lamb'}, {'Mary had', 'a little', 'lamb'}, {'Mary had', 'a', 'little lamb'}, {'Mary had', 'a', 'little', 'lamb'}
{'Mary', 'had a little lamb'}, {'Mary', 'had a little', 'lamb'}, {'Mary', 'had a', 'little lamb'} and so on...

Заранее спасибо:)

Ответы [ 3 ]

4 голосов
/ 21 января 2012

Подумайте об этом так: 

Mary <1> had <2> a <3> little <4> lamb

Каждый из этих <number> может быть как истинным, так и ложным.Если это правда, то вы сокращаете предложение в этом месте.

Итак, если у вас n + 1 слов, ваша проблема сводится к тому, чтобы пройти через двоичное представление чисел с n бит, то есть от 0 до2 ^ n-1

Примеры: 

0110 -> {'Mary had', 'a', 'little lamb'}
1111 -> {'Mary', 'had', 'a', 'little', 'lamb'}
0001 -> {'Mary had a little', 'lamb'}
1011 -> {'Mary', 'had a', 'little', 'lamb'}
2 голосов
/ 22 января 2012

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

string = "Mary had a little lamb";
set = StringSplit[string]
n = Length@set

{"Mary", "had", "a", "little", "lamb"}
5

Так что вам понадобится функция, которая разбивает предложение на слова (StringSplit).

Тогда вам понадобится функция для генерации целочисленных разбиений и функция перестановки, которая знает о дублированных элементах. Алгоритмы для обоих можно найти здесь, на StackOverflow. 

IntegerPartitions[n]

{{5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}}

Как только мы переставим каждый раздел («для каждого» - /@), мы получим все способы линейно разделить набор из пяти частей: 

parts = Join @@ Permutations /@ IntegerPartitions[n]

{{5}, {4, 1}, {1, 4}, {3, 2}, {2, 3}, {3, 1, 1}, {1, 3, 1},
 {1, 1, 3}, {2, 2, 1}, {2, 1, 2}, {1, 2, 2}, {2, 1, 1, 1}, {1, 2, 1, 1},
 {1, 1, 2, 1}, {1, 1, 1, 2}, {1, 1, 1, 1, 1}}

Наконец, нам нужна функция для разбиения набора в соответствии с последовательностями длин. Я называю мой динамический раздел: 

dynamicPartition[set, #] & /@ parts // Column

{{Mary,had,a,little,lamb}}
{{Mary,had,a,little},{lamb}}
{{Mary},{had,a,little,lamb}}
{{Mary,had,a},{little,lamb}}
{{Mary,had},{a,little,lamb}}
{{Mary,had,a},{little},{lamb}}
{{Mary},{had,a,little},{lamb}}
{{Mary},{had},{a,little,lamb}}
{{Mary,had},{a,little},{lamb}}
{{Mary,had},{a},{little,lamb}}
{{Mary},{had,a},{little,lamb}}
{{Mary,had},{a},{little},{lamb}}
{{Mary},{had,a},{little},{lamb}}
{{Mary},{had},{a,little},{lamb}}
{{Mary},{had},{a},{little,lamb}}
{{Mary},{had},{a},{little},{lamb}}
0 голосов
/ 21 января 2012

У вас есть 4 разделителя слов (пробелы) здесь. Каждый пробел может быть заменен (или нет) разделителем предложений. Таким образом, есть 16 = 2 ^ 4 случая, которые соответствуют двоичным числам 0000 ... 1111.

...