Permutation

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Jenderman
User
Beiträge: 5
Registriert: Freitag 7. März 2014, 23:42

Hallo,
ich habe einen Permutationsalgorithmus geschrieben, der auf Zufallszahlen aufbaut; Nur zum Spaß.

Code: Alles auswählen

__author__ = 'Jan_PC'
import random as rd
from math import factorial
from time import clock
from itertools import permutations


def random_permutation(to_perm):
    to_perm = list(to_perm)
    out = []
    while True:
        store = []
        while True:
            item = rd.choice(input)
            if item not in store and len(store) != len(to_perm):
                store.append(item)

            elif len(store) == len(to_perm):
                break

        if store not in out:
            out.append(store)

        if len(out) == factorial(len(to_perm)):
            break

    return out


a = clock()
print(random_permutation("ABC"))
b = clock()
meineversion = b-a


a = clock()
g = []
for i in (permutations("ABC")):
    g.append(i)
print(g)
b = clock()
deineversion = b-a

print("Meine Version:", meineversion, "Deine Version: ", deineversion)
Wie findet ihr das, wenn man von dem Nutzen absieht? :wink:

Meine Frage: Wie kann man iterativ einen "normalen" Algorithmus implementieren? Ich finde fast nur rekursive Ansätze.
BlackJack

@Jenderman: Ich finde das extrem umständlich. Falls ich richtig verstanden habe was das macht ist die einfachste und irgendwie auch naheliegenste Methode:

Code: Alles auswählen

def random_permutations(items):
    result = list(permutations(items))
    random.shuffle(result)
    return result
Das hat eine sehr voraussehbare Laufzeit, während Deins um so langsamer wird, je mehr Elemente es gibt, weil die Chance gegen Ende zufällig etwas auszuwürfeln was nicht schon enthalten ist, immer kleiner wird, und es dadurch immer länger dauert diese Treffer zu landen.

Edit: Zur zweiten Frage: Drück den rekursiven Ansatz Endrekursiv aus, dann lässt er sich auch sehr einfach iterativ ausdrücken.
Antworten