Как получить все одно и двух буквенные комбинации по порядку из слова?

Question

[eywsf]

Например, есть строка

String str = "program";

Необходимо получить все возможные комбинации, такие как:

• p-r-o-g-r-a-m
  
• p-r-o-g-r-am
  
• p-r-o-g-ra-m
  
• pr-og-r-am
  

ну и так далее.

Как это сделать на java? Или хотя бы общий алгоритм подскажите?

Сроку разбить не проблема, хоть по одному символу, хоть по два, например так

for (int i = 0; i < str.length()-1; i = i +2){
            String strTemp = str.charAt(i)+""+str.charAt(i+1);
              System.out.println(strTemp);
}

Но как получить (обойти) все возможные комбинации из одной и двух - непонятно, как запрограммировать.

Answer 1

[Alexandroppolus]

Самое простое рекуррентное соотношение:
Все раскладки по слову "program" - это, во первых, все раскладки для "rogram" с префиксом "p-", во вторых, все раскладки для "ogram" с префиксом "pr-". Ну и частные случаи слова из одной буквы и пустого. Вроде с таким подходом удобно будет применить StringBuffer

Comments

[Alexandroppolus]

Кстати, по такому соотношению выходит, что если слово из n букв, то раскладов всего F(n) штук, числа Фибоначчи
(для пустого слова считаем тоже один расклад)

Answer 2

[Antonio Solo]

p-r-o-g-r-a-m (0)

pr-o-g-r-a-m (1)
p-ro-g-r-a-m
p-r-og-r-a-m
p-r-o-gr-a-m
p-r-o-g-ra-m
p-r-o-g-r-am

pr-og-r-a-m (2)
pr-o-gr-a-m
pr-o-g-ra-m
pr-o-g-r-am
p-ro-gr-a-m
p-ro-g-ra-m
p-ro-g-r-am
p-r-og-ra-m
p-r-og-r-am
p-r-o-gr-am

pr-og-ra-m (3)
pr-og-r-am
pr-o-gr-am
p-ro-gr-am

я бы делал с использование рекурсии

Comments

[eywsf]

А можете набросать пример? Что-то я совсем туплю.

[Сергей Горностаев]

eywsf,

А можете набросать пример?

Здесь не пишут за вас готовых решений.

Что-то я совсем туплю

Кормен и Скиена помогают освежить разум. Если мне память не изменяет, у них рассматриваются задачи комбинаторики.

[eywsf]

Сергей Горностаев, спасибо. Я просто действительно не понимаю, как тут применить рекурсию.

Answer 3

[Sand]

7 букв, если в битах представить это 1111111, если перед первой буквой "-" не предусмотрено, то отсекаем её, получается 111111, допустим 0 - это "-" перед буквой, тогда циклом от 0 до 63 перебираем варианты, например: 110101 = pro-gr-am
000000 = p-r-o-g-r-a-m

Comments

[Сергей Соколов]

в вашем предложении биты – это межбуквенные пространства: там может быть либо связка (1) либо разрыв (0).
Но это не решает проблему длины: нельзя две 1 подряд. Букв должно быть не более 2 подряд по условию.

[Sand]

Сергей Соколов, согласен, пропустил