@
Egi ;
Zaciekawiło mnie zadanie drugie, więc pozwoliłem sobie zrobić (kod w Pythonie):
Kod:
import copy
def iterativePermutations(arr):
if len(arr) <= 1: return [arr]
else:
allPermutations = []
for i in range(0, len(arr)):
newarr = copy.copy(arr)
del newarr[i]
perms = iterativePermutations(newarr)
for perm in perms:
perm[0:0] = [arr[i]]
allPermutations[-1:-1] = perms
return allPermutations
def _recursivePermutations(arr, n, acc):
if n == 0: return acc
elif len(arr) <= 1: return [arr]
else:
newarr = copy.copy(arr)
del newarr[n - 1]
perms = _recursivePermutations(newarr, len(newarr), [])
for perm in perms:
perm[0:0] = [arr[n - 1]]
return _recursivePermutations(arr, n - 1, acc + perms)
def recursivePermutations(arr):
return _recursivePermutations(arr, len(arr), [])
def _nonTailrecursivePermutations(arr, n):
if n == 0: return []
elif len(arr) <= 1: return [arr]
else:
newarr = copy.copy(arr)
del newarr[n - 1]
perms = _nonTailrecursivePermutations(newarr, len(newarr))
for perm in perms:
perm[0:0] = [arr[n - 1]]
return perms + _nonTailrecursivePermutations(arr, n - 1)
def nonTailrecursivePermutations(arr):
return _nonTailrecursivePermutations(arr, len(arr))
Trochę objaśnień. Idea algorytmu znajdującego permutacje jest taka: dla każdego elementu, oblicz wszystkie permutacje wszystkich pozostałych elementów i wstaw do nich ten element na początek. Jak widać, rekurencja nasuwa się sama. Warunkiem kończącym jest długość tablicy ≤ 1 — wtedy nie ma już czego permutować (musimy tylko zapakować naszą tablicę w dodatkową tablicę, bo wynikiem ma być tablica permutacji). W wersji iteracyjnej robimy sobie najpierw tablicę na wyniki, a potem wykonujemy algorytm tak jak opisałem na początku. W wersji rekurencyjnej jest trudniej — nie mamy iteracji, więc jako parametr funkcji musimy podać indeks elementu, który będziemy wstawiać na początek permutacji reszty tablicy. Dochodzi nam przez to jeden warunek: jeżeli doszliśmy do n = 0, to zwracamy akumulator z naszymi permutacjami. Potem postępujemy podobnie jak poprzednio. Uwagi techniczne: przypisanie w Pythonie jest upośledzone i zamiast kopiować, przypisuje referencję. W drugim algorytmie pojawia się iteracja (kiedy wrzucamy element na początek), ale można ją zastąpić czymś w stylu
Kod:
map (prepend el) perms
— nie znam się na Pythonie, więc nie bawiłem się w to.
@edit
Jest też wersja bez rekurencji ogonowej, która chyba wygląda trochęNIEDOZWOLONY_CIAG_ZNAKOWmniej groźnie.