Żeby zrozumieć rekurencję, trzeba zrozumieć rekurencję
Niedawno spotkałem się z koniecznością wygenerowania wszystkich kombinacji* pinów na potrzeby bruteforce'a i przy okazji zacząłem się zastanawiać w jaki sposób można by to zaimplementować we własnym zakresie.
*ściśle mówiąc permutacji z powtórzeniami
Każdy rozsądny człowiek otworzyłby google i po wpisaniu "python pin permutations" znalazł na stack-overflow'le funkcję product w bibliotece itertools. Funkcja ta generuje nam iloczyn kartezjański z danych wejściowych i właściwie nie wymaga zrozumienia istoty problemu. To byłoby pythonowskie podejście do sprawy.
Jednak nie uważam się za człowieka rozsądnego, więc zacząłem roztrząsać problem. Jak powinien wyglądać program, który wygeneruje nam wszystkie zestawienia liter albo cyfr?
Co dostajemy na wejściu?
A B C D - listę elementów. Cokolwiek.
Co mamy dostać na wyjściu?
Wszystkie permutacje, bez względu na to czy się powtarzają czy nie. Kolejność ma znaczenie.
AAAA
AAAB
AAAC
AAAD
AABA
AABB
AABC
AABD
itd...
1 results, final_results = permutate(element_list, depth+1, results, final_results)
2 File "./permutacje.py", line 8, in permutate
3 results, final_results = permutate(element_list, depth+1, results, final_results)
4 File "./permutacje.py", line 8, in permutate
5 results, final_results = permutate(element_list, depth+1, results, final_results)
6 File "./permutacje.py", line 8, in permutate
7 results, final_results = permutate(element_list, depth+1, results, final_results)
8 File "./permutacje.py", line 8, in permutate
9 results, final_results = permutate(element_list, depth+1, results, final_results)
10 File "./permutacje.py", line 8, in permutate
11 results, final_results = permutate(element_list, depth+1, results, final_results)
12 RecursionError: maximum recursion depth exceeded
To jest 1000.
Poniżej umieściłem działającą funkcję, która robi dokładnie to, czego chciałem.
1 #!/usr/bin/env python3
2
3 def permutate(element_list, depth, results, final_results):
4
5 # Iteruj po wszystkich elementach listy.
6 for element in element_list:
7
8 # Dopóki rekurencja nie osiągnęła głębokości równej ilości elementów w liście, schodź niżej.
9 if depth < len(element_list):
10 results[depth] = element
11 results, final_results = permutate(element_list, depth+1, results, final_results)
12 else:
13 results[depth] = element
14 final_results.append(''.join(results.values()))
15
16 # Na tym etapie funkcja się kończy i wracamy o piętro wyżej.
17 return results, final_results
18
19
20 element_list = ['A', 'B', 'C', 'D', ]
21
22 results, final_results = permutate(element_list, 1, {}, [])
23
24 # Tutaj małe łatanie taśmą - set() likwiduje wszystkie duplikaty z listy.
25 result_set = set(final_results)
26 print(result_set)
27 print(len(result_set))
Na wyjściu program wydaje z siebie taki wynik:
1 {'ABBD', 'DDCC', 'ACDD', 'CABD', 'CBCB', 'BADA', 'CDBB', 'CACD', 'BBBD', 'AADC',
2 'AAAA', 'DADC', 'DCDD', 'BBAD', 'DDAB', 'ADBB', 'BBDB', 'ABDC', 'BADD', 'ACAC',
3 'DDAD', 'ADDB', 'CBBA', 'DDBB', 'DDBD', 'DCCC', 'CDAB', 'ABDB', 'CCDC', 'DBAB',
4 'BACA', 'ACAA', 'BABB', 'DBBB', 'BBDA', 'CADA', 'ADCA', 'BAAC', 'ACCC', 'BCBC',
5 'CCDD', 'ACBA', 'CDCC', 'ADCD', 'BDBD', 'AACA', 'BCCC', 'DACD', 'ACCA', 'DDDC',
6 'ABDD', 'CADC', 'ACCD', 'BBDC', 'CBDA', 'ABDA', 'AADD', 'DBCA', 'ACBB', 'BBDD',
7
8 (...)
9
10 256
Zastanawiałem się też nad rzędem złożoności obliczeniowej algorytmu wykorzystanego w tej funkcji. Prawdopodobnie jest to O(n^n), ponieważ każdy kolejny element w liście powoduje zejście o kolejne piętro w dół w rekurencji i tym samym liczba kroków algorytmu wzrasta do potęgi n.
Na wkresie wyglądałoby to tak:
Czyli dość kiepsko.