Das deutsche Python-Forum

Brauche Hilfe bei "Kombinations-/Varianten-Algorithmus"

Hallo,

ich habe folgendes Problem:

ich habe einen String, z.B. 'abcde'.
Zwischen jeden Buchstaben will ich jetzt eine bestimmte Anzahl an Punkten einfügen. Zwischen jedem Buchstaben können 0 bis $n Punkte sein.

Irgendwie will ich jetzt alle möglichen Varianten herausfinden, die man so bilden kann.

Beispiel-Strings wären z.B. ($n = 5):
'a.bcde'
'a.b..c....de'
'a.....b.....c.....d.....e'

Eigentlich hört sich das ja erstmal ganz simpel an. Irgendwie bin ich allerdings nicht in der Lage mir einen Algorithmus dafür zu überlegen (Ich habe das Gefühl mein "RAM" läuft voll, wenn ich versuche eine Lösung zu finden, bei der auch wirklich alle Varianten gefunden werden

)

Kann mir jemand einen Tipp geben, wie man so etwas am besten löst?

So mal auf die Schnelle:

Code: Alles auswählen

def spam(word, n, seperator="."):
    if len(word) < 2:
        yield word
    else:
        for i in range(n+1):
            for w in points(word[1:], n):
                yield "".join((word[0], seperator*i, w))

Vielen Dank.

Mit fertigem Code hätte ich gar nicht gerechnet, aber umso besser

points() ist doch eine Funktion, oder? Die hast du dann nämliche vergessen zu posten.

PS: was meinst du eigentlich mit Spam? (Das der Output auf dem ersten Blick keinen Sinn ergibt?) . Witzigerweise hat das ganze nämliche sogar mit Spam zu tun, bzw. mit der Bekämpfung von Spam

ändere mal points() in spam() um, dann klappts auch

(Ist doch ne rekursive Funtkion - sonst funzt der Algo nicht)

Statt range() sollte man noch xrange() nehmen, dann wirds noch ne ecke schneller.

Danke, so funktioniert es

Hyperion hat das schon richtig erkannt, ich habe den geänderten Code nicht noch mal getestet.

Zu xrange vs. range: ich bin schon Python 3.0 kompatibel