Python :: Aufgabe #308
2 Lösungen
Bonusaufgabe 5 (schwer) - Permutationen.
Profi - Python
von Yali23
- 09.11.2020 um 17:21 Uhr
Implementieren Sie eine rekursive Funktion permute, die alle Permutationen der Elemente eines sequentiellen Datentyps (Slice-Operator wird unterstützt) bestimmt und als Elemente einer Liste ausgibt.
Beispieloutput:
Python-Code
Beispieloutput:
Python-Codepermute("abc")
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
# Führen Sie diese Zelle aus, um Ihre Funktion zu testen.
# Wenn das Ausführen dieser Zelle zu Fehlern führt, dann ist Ihre Implementierung vermutlich nicht korrekt.
assert sorted(permute("abc")) == sorted(['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
assert sorted(permute("ab")) == sorted(['ab', 'ba'])
assert sorted(permute([1, 2])) == sorted([[1, 2], [2, 1]])
assert sorted(permute((1, 2, 3))) == sorted([(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)])Lösungen:
Ich bin mir nicht sicher, ob die Typunterscheidung so optimal implementiert ist. Es funktioniert aber.
Python-Code
Python-Code
from math import factorial
def permute(data):
if isinstance(data, list):
data_type = 'list'
if isinstance(data, tuple):
data = list(data)
data_type = 'tuple'
if isinstance(data, str):
data = list(data)
data_type = 'string'
result_length = factorial(len(data))
if len(data) <= 1:
return [data]
else:
perm = []
for index in range(len(data)):
for P in permute(data[:index] + data[index+1:]):
perm.append([data[index]] + P)
if data_type == 'list':
return perm
if data_type == 'tuple':
if len(perm) == result_length:
new_perm = []
for element in perm:
new_perm.append(tuple(element))
return new_perm
else:
return perm
if data_type == 'string':
if len(perm) == result_length:
new_perm = []
for element in perm:
new_perm.append(''.join(element))
return new_perm
else:
return perm
print(permute('abc'))
print(permute('ab'))
print(permute([1,2]))
print(permute((1,2,3)))
assert sorted(permute("abc")) == sorted(['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
assert sorted(permute("ab")) == sorted(['ab', 'ba'])
assert sorted(permute([1, 2])) == sorted([[1, 2], [2, 1]])
assert sorted(permute((1, 2, 3))) == sorted([(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)])
Python-Code
# 308 Bonusaufgabe 5 (schwer) - Permutationen.
import itertools
def permute(element):
liste= []
for i in itertools.permutations(element):
if type(element) == str:
liste.append(''.join(i))
elif type(element) == list:
l = []
for e in i:
l.append(e)
liste.append(l)
else:
liste.append(i)
return liste
# Führen Sie diese Zelle aus, um Ihre Funktion zu testen.
# Wenn das Ausführen dieser Zelle zu Fehlern führt, dann ist Ihre Implementierung vermutlich nicht korrekt.
assert sorted(permute("abc")) == sorted(['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
assert sorted(permute("ab")) == sorted(['ab', 'ba'])
assert sorted(permute([1, 2])) == sorted([[1, 2], [2, 1]])
assert sorted(permute((1, 2, 3))) == sorted([(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)])