alle kombinationen von zeichen in einem string

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.
abgdf

Beitragvon abgdf » Freitag 31. Oktober 2008, 20:45

Hier noch eine mögliche Übersetzung des obigen C-Codes nach Python (zum besseren Verständnis) (die Funktion "permut" ruft sich dauernd selbst auf :shock:):

Code: Alles auswählen

#!/usr/bin/env python
#-*- coding: iso-8859-1 -*-

def swap(c, firstIndex, secondIndex):

    a = ""

    for i in range(len(c)):

        if i == firstIndex:
            tmp = c[i]
            a += c[secondIndex]
            continue

        if i == secondIndex:
            a += tmp
            continue

        a += c[i]

    return a


def permut(c, endIndex):

    if endIndex == 0:
        print c

    else:
        permut(c, endIndex - 1);

        for i in range(endIndex):
            c = swap(c, i, endIndex)
            permut(c, endIndex - 1)
            c = swap(c, i, endIndex)
 
c = raw_input("Eingabe Wort: ")
permut(c, len(c) - 1)

Gruß
DasIch
User
Beiträge: 2405
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Freitag 31. Oktober 2008, 20:57

abgdf hat geschrieben: (die Funktion "permut" ruft sich dauernd selbst auf :shock:):

Das nennt sich Rekursion.
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Beitragvon yipyip » Freitag 31. Oktober 2008, 22:55

Rekursion ist, wenn man's rekursiv definiert...

Code: Alles auswählen

def nperm(ls, n):

  if n == 0:
    yield []
  else:
    for i in xrange(len(ls)):
      for c in nperm(ls[:i] + ls[i+1:], n-1):
        yield c + [ls[i]]

strg = 'eis'
result = []
for i, s in enumerate(strg):
  result.extend([''.join(p) for p in nperm(list(strg), i+1)])

print result


Bitte nicht mit einem String der Länge 14 ausprobieren!
:wink:
yipyip
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Samstag 1. November 2008, 09:30

Wobei Rekursion in Python generell nicht so spaßig ist, da man ein Rekursionslimit hat und da durchaus auch ankommen kann. Vor allem wenn man die Rekursion falsch formuliert ;)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasIch
User
Beiträge: 2405
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Sonntag 2. November 2008, 18:13

Python 2.6 ftw.

Code: Alles auswählen

In [33]: from itertools import permutations, combinations

In [34]: foo = 'eis'

In [35]: for i in xrange(len(foo) + 1):
   ....:     for combination in combinations(foo, i):
   ....:         for permutation in permutations(combination):
   ....:             permutation
   ....:
   ....:
Out[35]: ()
Out[35]: ('e',)
Out[35]: ('i',)
Out[35]: ('s',)
Out[35]: ('e', 'i')
Out[35]: ('i', 'e')
Out[35]: ('e', 's')
Out[35]: ('s', 'e')
Out[35]: ('i', 's')
Out[35]: ('s', 'i')
Out[35]: ('e', 'i', 's')
Out[35]: ('e', 's', 'i')
Out[35]: ('i', 'e', 's')
Out[35]: ('i', 's', 'e')
Out[35]: ('s', 'e', 'i')
Out[35]: ('s', 'i', 'e')
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Sonntag 2. November 2008, 19:48

Das ist ja genau das, was ich schon in meinem ersten Posting (allerdings ohne Code) gesagt hatte: In Python 2.6 schnell erledigt. Hat mich die ganze Zeit gewundert, warum so lange daran herumgebastelt wurde ... :)
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Beitragvon yipyip » Sonntag 2. November 2008, 20:13

In Python 5000 werden wir dann endlich haben:

Code: Alles auswählen

from all_problems import my_problem
my_problem.solve()

:) :wink:
yipyip
DasIch
User
Beiträge: 2405
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Sonntag 2. November 2008, 20:52

yipyip hat geschrieben:In Python 5000 werden wir dann endlich haben[...]

Ach was, hab ich jetzt schon:

Code: Alles auswählen

In [11]: import sys

In [12]: from types import ModuleType

In [13]: sys.modules['all_problems'] = ModuleType('all_problems')

In [14]: class my_problem(object):
   ....:        @staticmethod
   ....:        def solve():
   ....:                return 42
   ....:

In [15]: sys.modules['all_problems'].my_problem = my_problem

In [16]: from all_problems import my_problem

In [17]: my_problem.solve()
Out[17]: 42
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Sonntag 2. November 2008, 21:09

yipyip hat geschrieben:In Python 5000 werden wir dann endlich haben:

Code: Alles auswählen

from all_problems import my_problem
my_problem.solve()

:) :wink:
yipyip


Dann wird's aber langweilig :cry:
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Beitragvon yipyip » Sonntag 2. November 2008, 21:26

@DasIch:
Danke, ...hat mich wieder mal verblüfft, was man
in Python alles anstellen kann. :)

@numerix:
Nicht traurig sein, in diesem Forum
wird es auch weiterhin genug zu tun geben. :)

:wink:
yipyip
DasIch
User
Beiträge: 2405
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Sonntag 2. November 2008, 21:44

yipyip hat geschrieben:@DasIch:
Danke, ...hat mich wieder mal verblüfft, was man
in Python alles anstellen kann. :)

Wenn du daran interessiert bist schau dir mal Zine an, dort wird das Produktiv genutzt um ein Datenbank Modul zu erzeugen, ziemlich coole Sache.
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Beitragvon roschi » Samstag 8. November 2008, 10:55

MERCI!

der C-code, den abgdf gepostet hat, funktioniert wunderbar schnell. leider kenne ich mich mit C so gut wie gar nicht aus. koennte mir vielleicht jemand sagen, wie man den code so erweitern koennte, dass er auch teilstrings erzeugt, und nicht nur alle kombinationen (das sind ja jetzt wirklich kombinationen :))?

außerdem habe ich mir mal python 2.6 zusaetzlich installiert, und das hier ausprobiert:

Code: Alles auswählen

def perm(s):
    for i in xrange(len(s) + 1):
        for combination in combinations(s, i):
            for permutation in permutations(combination):
                if permutation:
                    print "".join(permutation)

perm("eis")

klappt auch wunderbar, ist nur - was ja auch logisch ist - deutlich langsamer als die methode in C, die ich eben bevorzugen wuerde.

lg
roschi
Fuer Alle, die in Python einsteigen wollen, kann ich das Buch A Byte of Python nur waermstens empfehlen!
Mad-Marty
User
Beiträge: 317
Registriert: Mittwoch 18. Januar 2006, 19:46

Beitragvon Mad-Marty » Samstag 8. November 2008, 12:55

Wie wärs denn wenn du diesen unsinnigen ansatz mit liste generieren komplett verwirfst?

Soll bestimmt ein Passwortcracker per Bruteforce werden oder?

Auf einem normalen Rechner wirst du wohl mit einem generator arbeiten müssen, dann brauchst du auch nicht soviel RAM.

Alles andere halte ich für ausserhalb deiner hardwaremöglichkeiten ...
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Beitragvon roschi » Samstag 8. November 2008, 18:50

hallo!

@Mad Marty:
die liste habe ich jetzt rausgenommen. ist ja klar, das es damit bei so großen nicht klappen kann. ich gebe jetzt alles nach stdout aus und leite es in eine datei um.
nein, es soll kein bruteforce passwort cracker werden. ich moechte am ende jedes ergebnis auf presens in einem woerterbuch pruefen, um alle sinnvollen woerter aus dem ursprungs-string zu erhalten.

lg
roschi

PS: ich habe von etwa um 11:00 uhr bis jetzt 81 GB an daten mit der python-methode erzeugt.
Fuer Alle, die in Python einsteigen wollen, kann ich das Buch A Byte of Python nur waermstens empfehlen!
DasIch
User
Beiträge: 2405
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Samstag 8. November 2008, 18:53

Wie wäre es mit Kölner Phonetik oder Soundex?

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder