Bonusaufgabe 5 (schwer) - Permutationen. - Lösung #1TRAIN your programmer

2 Lösungen

#308

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

permute("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)])

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von Klaus (1960 Punkte) - 01.12.2020 um 23:56 Uhr

Ich bin mir nicht sicher, ob die Typunterscheidung so optimal implementiert ist. Es funktioniert aber.

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)])