Как получить перестановки строки без повторения, используя рекурсию, но без циклов for или while? - PullRequest
Новая
       11

Как получить перестановки строки без повторения, используя рекурсию, но без циклов for или while?

1 голос
/ 05 мая 2019

Я изучаю Python и алгоритмы сортировки. Я хочу найти перестановки этой строки «AAABB», без повторений. Я должен получить ответ без использования циклов for и while, только рекурсия.

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

  1. Всегда будет возвращать A, если доступно

  2. Всегда будет возвращать B, если доступно, и

  3. W не вернет ничего, если не осталось доступных букв.

Пока я пробовал этот код: 

#n1 = Amount of A available 
#l1 = character A
#n2 = Amount of B available
#l2 = character B

def perm(n1,l1,n2,l2):
 if n1 == 0: # Run out of A?
     if n2 == 0: # Yes, no A left. Run out of B?: 
         return '\n' # Yes, no A nor B left, then do nothing
     else: # No, still have B, then:
         return l2 + perm(n1,l1,n2-1,l2) # Return B

 else: # No, still have A, then :
     if n2 == 0: # Run out of B?
         return l1 + perm(n1-1,l1,n2,l2)  # Yes, no B left, then return A
     else: # No, still have B, then:
         return l1+perm(n1-1,l1,n2,l2) + l2+perm(n1,l1,n2-1,l2) # Return both

print(perm(3,'A',2,'B'))

Этот код возвращает 10 неполных перестановок:
AAABB BAB BA BAAB BA BAA BAAAB BA BAA BAAA

Я ожидаю получить 10 полных перестановок:
AAABB AABBA AABAB ABBAA ABABA ABAAB BAABA BAAAB BABAA BBAAA.

Есть ли у вас какие-либо идеи о том, как я могу улучшить свой код или какое условие мне не хватает?

1 Ответ

1 голос
/ 05 мая 2019

Во-первых, в вашем подходе 4 случая.

  1. n1 == 0 and n2 == 0 возврат '\n'
  2. n1 >= 1 and n2 == 0 возвращает n1 * l1 + '\n'
  3. n1 == 0 and n2 >= 1 возвращает n2 * l2 + '\n'
  4. n1 >= 1 and n2 >= 1 возвращает l1 + perm(...) и возвращает l2 + perm(...)

И проблема в четвертом случае. так как вы используете стек вызовов для соединения строки, вы получаете частичную запись обратно.

  1. AAABB
  2. ^^BAB
  3. ^^^BA
  4. ^BAAB
  5. ^^^BA
  6. ^^BAA
  7. BAAAB
  8. ^^^BA
  9. ^^BAA
  10. ^BAAA

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

решение состоит в том, чтобы сохранить свой собственный список предшествующих символов и добавить их перед тривиальным регистром (1). 

    def perm(n1, l1, n2, l2, prefix=""):
        if n1 == 0 and n2 == 0:
            return prefix + '\n'
        elif n1 >= 1 and n2 >= 1:
            return perm(...) + perm(...)
        ...
        elif n1 >= 1 and n2 == 0:
            return perm(..., prefix+l1)
...