Перестановки, Рекурсия

У меня есть задание: пользователь вводит строку, например ABCD, и программа должна выдать все перестановки. Мне не нужен весь код, просто совет. это то, что я получил до сих пор, я ничего не реализовал.

Возьмем ABCD в качестве примера:

получить факториал длины строки в этом случае 4! = 24.

24/4 = 6 Итак, первая буква должна измениться после 6. Пока все хорошо.

чем получить факториал оставшихся букв, которые равны трем 3! = 6.

6/3 = 2 2 места для каждой буквы. отсюда я не знаю, как он может продолжать заполнять 24 места.

С этим алгоритмом все, что у меня будет, это

АВСD

АБД

AC

AC

AD

AD

B

B

B

B

B

B

.

. (продолжение с 6 C и 6 D)

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

Спасибо! Если что-то не ясно, укажите.


java recursion permutation
person John Smith    schedule 25.03.2011    source источник
comment
Спасибо! Вы имели в виду, как это правильно?   -  person John Smith    schedule 26.03.2011
comment
Permutations.java   -  person Paolo Falabella    schedule 26.03.2011
comment
Да, это может изменить небольшой пример перестановки, входящей в ABC - это ее перестановки ABC,ACB,BAC,BCA,CAB,CBA.   -  person John Smith    schedule 26.03.2011

Ответы (2)


arrow_upward
4
arrow_downward

Вы правы, что рекурсия - это путь. Пример, над которым вы работали с небольшим количеством математики, был правильным, но отчасти косвенным.

Вот некоторый псевдокод:

 def permute(charSet, soFar):
     if charSet is empty: print soFar //base case
     for each element 'e' of charSet:
         permute(charSet without e, soFar + e)  //recurse

пример дерева частичной рекурсии

                      permute({A,B,C}, '')
                   /           |           \
 permute({B,C}, 'A')  permute({A,C}, 'B')   permute({A,B}, 'C')   
                          /          \
               permute({A}, 'BC')    permute({C}, 'BA')
                       |
               permute({}, 'BCA')<---BASE CASE, print 'BCA'

РЕДАКТИРОВАТЬ

Для обработки повторяющихся символов без дублирования каких-либо перестановок. Пусть unique будет функцией удаления любых повторяющихся элементов из коллекции (или строки, которая обрабатывается как упорядоченная коллекция символов посредством индексации).

1) Сохраняйте результаты (включая дубликаты), затем отфильтровывайте их

 def permuteRec(charSet, soFar):
     if charSet is empty: tempResults.add(soFar) //base case
     for each element 'e' of charSet:
         permute(charSet without e, soFar + e)  //recurse

 global tempResults[]

 def permute(inString):
     permuteRec(inString, '')
     return unique(tempResults)

 print permute(inString)

2) Избегайте создания дубликатов в первую очередь

 def permute(charSet, soFar):
     if charSet is empty: print soFar //base case
     for each element 'e' of unique(charSet):
         permute(charSet without e, soFar + e)  //recurse
person jon_darkstar    schedule 25.03.2011
comment
Можете ли вы объяснить немного подробнее, потому что я не совсем понял это, поэтому базовым случаем будет пустая строка? мое представление о базовом случае было пустым и состояло всего из 1 символа строки. - person John Smith; 26.03.2011
comment
Мой базовый случай: если длина строки меньше 2, напечатайте 0 для пустой строки, ту же строку для строки из 1 символа. - person John Smith; 26.03.2011
comment
при первом вызове charSet будет коллекцией, содержащей все n элементов, а soFar будет пустой. в базовых случаях charSet будет пустым, а soFar будет содержать все n элементов. soFar необходимо заказывать, charSet можно заказывать или не заказывать - person jon_darkstar; 26.03.2011
comment
я действительно не понимаю вашу идею базового случая. какую строку вы имеете в виду, когда говорите «длина строки»? - person jon_darkstar; 26.03.2011
comment
Большое спасибо за помощь. Знаете ли вы какие-либо упражнения для улучшения рекурсии? - person John Smith; 26.03.2011
comment
Строка, которую вводит пользователь, если она состоит всего из одной буквы или пуста. Я думаю, что смотрю на эту проблему с неправильной стороны. - person John Smith; 26.03.2011
comment
Спасибо за вашу помощь! Я понял это и надеюсь, что с вашими предложениями рекурсия улучшится. - person John Smith; 26.03.2011
comment
упражнения на рекурсию - напишите рекурсивную факториальную функцию (это хвостовая рекурсия, вызов одиночной рекурсии, также может выполняться итеративно), попробуйте реализовать сортировку слиянием после этого (бинарная рекурсия), ознакомьтесь с древовидными структурами (это рекурсивная структура) и реализуйте один. напишите что-нибудь для последовательности фибоначчи. проверьте связанные вопросы справа. добавьте распечатку аргументов в начале каждого вызова рекурсии, чтобы вы могли следить, куда идет рекурсия (или использовать языковую конструкцию для трассировки стека) и ознакомиться со стеком. вам как бы нужно построить интуицию для этого. - person jon_darkstar; 26.03.2011
comment
у вас не было плохой идеи с «Строкой, которую вводит пользователь, если она состоит всего из одной буквы или пуста», но помните, что это не обязательно должно быть то, что вводит пользователь, это может быть несколько слоев рекурсии позже. это просто должно быть аргументом функции. - person jon_darkstar; 26.03.2011
comment
Что, если пользователь введет строку, содержащую повторяющиеся символы, например "AABC"? - person Elian Ebbing; 26.03.2011
comment
Псевдокод, который я первоначально опубликовал, не учитывал это и поэтому выдавал некоторые дубликаты. С этим не так уж сложно справиться, я опубликовал два способа. - person jon_darkstar; 26.03.2011

arrow_upward
0
arrow_downward

Создайте метод, который принимает строку.

Выберите букву из строки и выведите ее.

Создайте новую строку с входной строкой за вычетом выбранной буквы.

вызовите вышеуказанный метод с новой строкой, если она имеет хотя бы 1 символ

сделать это выбор одной буквы для каждой возможной буквы.

person MeBigFatGuy    schedule 25.03.2011