Brauche Hilfe bei "Kombinations-/Varianten-Algorithmus

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.
Gero
User
Beiträge: 3
Registriert: Freitag 1. August 2008, 17:45

Brauche Hilfe bei "Kombinations-/Varianten-Algorithmus

Beitragvon Gero » Freitag 1. August 2008, 17:59

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?
EyDu
User
Beiträge: 4868
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Freitag 1. August 2008, 18:21

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))
Gero
User
Beiträge: 3
Registriert: Freitag 1. August 2008, 17:45

Beitragvon Gero » Freitag 1. August 2008, 18:42

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 :)
Benutzeravatar
Hyperion
Moderator
Beiträge: 7472
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Beitragvon Hyperion » Freitag 1. August 2008, 18:56

ä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.
Gero
User
Beiträge: 3
Registriert: Freitag 1. August 2008, 17:45

Beitragvon Gero » Freitag 1. August 2008, 19:01

Danke, so funktioniert es :D
EyDu
User
Beiträge: 4868
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Freitag 1. August 2008, 19:41

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

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]