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.
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Donnerstag 30. Oktober 2008, 22:06

hallo!

ich braeuchte wieder einmal eure hilfe, um etwas zu realisieren:
ich habe einen string - zum beispiel 'eis'. jetzt will ich aus diesem string alle kombinationen der zeichen haben. bei 'eis' waere das also:
'eis', 'sie', 'sei', 'ies', 'ise', 'esi', 'ei', 'ie', 'es'. 'se'. 'e'. 'i', 's'

kann mir jemand sagen, wie ich das anstellen koennte?

lg
roschi

PS: es sollte auch so schnell sein, dass man es bei einem 14-zeichen-langen string anwenden kann, ohne seinen rechner eine woche dafuer opfern zu muessen :)
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Donnerstag 30. Oktober 2008, 22:28

roschi hat geschrieben:ich habe einen string - zum beispiel 'eis'. jetzt will ich aus diesem string alle kombinationen der zeichen haben. bei 'eis' waere das also:
'eis', 'sie', 'sei', 'ies', 'ise', 'esi', 'ei', 'ie', 'es'. 'se'. 'e'. 'i', 's'
Das sind keine Kombinationen, sondern Variationen, da es dir ja auch auf die Reihenfolge ankommt. Im übrigen hast du wohl 'si' und 'is' vergessen, oder?
roschi hat geschrieben:PS: es sollte auch so schnell sein, dass man es bei einem 14-zeichen-langen string anwenden kann, ohne seinen rechner eine woche dafuer opfern zu muessen :)
Das wird schwierig, denn bei 14 Zeichen Länge gibt es 236.975.164.804 Möglichkeiten ... :)

Ansonsten: Sieh dir doch mal das itertools-Modul an, falls du Python 2.6 nutzt. Da sind neue Funktionen hinzugekommen, die auf deine Problemstellung passen.
abgdf

Freitag 31. Oktober 2008, 00:30

Vielleicht kannst Du auch die Stellen der Buchstaben in Zahlen umwandeln und dann mit "random.shuffle()" arbeiten. Natürlich nicht bei 14 Zeichen ...
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Freitag 31. Oktober 2008, 00:47

numerix hat geschrieben:Das wird schwierig, denn bei 14 Zeichen Länge gibt es 236.975.164.804 Möglichkeiten ... :)
Ich komme mit bei 14 Zeichen auf einen "etwas" größeren Wert von 29.192.926.025.390.624

Bild

Code: Alles auswählen

\sum_{i=1}^{14}\binom{14}{i}14^i = 29.192.926.025.390.624
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 31. Oktober 2008, 10:28

EyDu hat geschrieben:
numerix hat geschrieben:Das wird schwierig, denn bei 14 Zeichen Länge gibt es 236.975.164.804 Möglichkeiten ... :)
Ich komme mit bei 14 Zeichen auf einen "etwas" größeren Wert von 29.192.926.025.390.624
14!/0! + 14!/1! + 14!/2! + ... + 14!/13! = 236.975.164.804
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 31. Oktober 2008, 10:31

abgdf hat geschrieben:Ich glaube, das Problem ist mathematisch nicht so ganz leicht:
Das ist relativ. Anspruchslos ist es nicht, jedenfalls nicht, wenn man die entsprechenden Funktionen selbst schreibt.

Ich hatte ja schon auf die itertools aus Python 2.6 hingewiesen - damit sollte es an sich auch für mathematisch weniger Versierte kein Problem sein - sieht man von der Laufzeit bei 14 Zeichen ab ...
Benutzeravatar
roschi
User
Beiträge: 225
Registriert: Samstag 29. März 2008, 18:58
Wohnort: Thueringen, Deutschland
Kontaktdaten:

Freitag 31. Oktober 2008, 10:47

hallo!

vielen dank fuer die antworten!
ja, ihr habt recht. der begriff 'kombinationen' ist da nicht wirklich zutreffend. :(

@numerix:
nein, ich nutze noch python 2.5.1. wenn dann 3.0 mal rauskommt stelle ich komplett um. allerdings koennte ich mir fuer diese sache ja mal 2.6 installieren

ich habe mir jetzt jedenfalls folgendes zusammengebastelt:

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-

import cPickle, sys

def permu(s):
    if len(s) < 2:
      return set(s)
    else:
      result = set()
      for perm in permu(s[1:]):
        result.update([s[0].join((perm[:i], perm[i:]))
                                  for i in range(len(perm) + 1)])
      return result

data = set()
for i in xrange(1, len(sys.argv[1]) + 1):
    print "%d/%d" % (i, len(sys.argv[1])),
    data.update(permu(sys.argv[1][:i]))

f = file("out", "wb")
cPickle.dump(data, f)
f.close()
es funktioniert fast richtig - wenn auch sehr langsam. die permu-funktion habe ich - wenn auch ein wenig geaendert - von abgdf's link (http://procrastinationrising.com/2007/0 ... on-python/) nun muss ich es nur noch schaffen, dass er auch wirklich ALLE variationen durchprobiert. die for-schleife war da also doch nicht so angebracht...

lg und vielen vielen dank schonmal
roschi

PS: was meint ihr: wie lange wird ein rechner mit 2 GHz CPU fuer 14 zeichen brauchen - und wird mein ram dieses riesige set verkraften?
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Freitag 31. Oktober 2008, 12:14

Für Permutationen habe ich mir dieses Script geschrieben (prä-2.6/3.0). Allerdings erzeuge ich dort nur Wörter mit der selben Länge wie die Ausgangszeichenfolge und nicht, wie im ersten Beitrag zu sehen, auch Teilstrings davon.
BlackJack

Freitag 31. Oktober 2008, 12:18

@roschi: Nimm doch einfach mal Numerix' Zahl als Grundlage. Selbst wenn jeder Eintrag im Ergebnis nur ein Byte belegen würde, hätten wir ca. 220 Gigabyte an Daten.

Wenn jeder Eintrag in einer Microsekunde berechnet wird, sind das ca. 65 Stunden Rechenzeit.

Den Sprung von Python 2.5 zu Python 3.0 würde ich nicht empfehlen, jedenfalls nicht für die Migration von vorhandenem Quelltext. Die 2.6 ist explizit darauf vorbereitet beim Umstieg zu helfen. Man kann einiges was sich in 3.0 ändert, in der 2.6 aus `__future__` importieren und es gibt Warnungen für Sachen, die sich ändern. Ausserdem wird es das `2to3.py` wohl nicht für 2.5 geben, jedenfalls nicht offiziell.
DasIch
User
Beiträge: 2452
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Freitag 31. Oktober 2008, 14:57

roschi hat geschrieben:ich habe mir jetzt jedenfalls folgendes zusammengebastelt[...]
Wäre ein rekursiver Generator bei Permutationen nicht sinnvoller?

Code: Alles auswählen

In [1]: def permutations(s):
   ...:     if len(s) <= 1:
   ...:         yield s    
   ...:         raise StopIteration
   ...:     for index, element in enumerate(s):
   ...:         rest = s[:index] + s[index + 1:]
   ...:         for perm in permutations(rest):
   ...:             yield element, perm
Qubit
User
Beiträge: 75
Registriert: Dienstag 7. Oktober 2008, 09:07

Freitag 31. Oktober 2008, 15:07

roschi hat geschrieben:hallo!

ich braeuchte wieder einmal eure hilfe, um etwas zu realisieren:
ich habe einen string - zum beispiel 'eis'. jetzt will ich aus diesem string alle kombinationen der zeichen haben. bei 'eis' waere das also:
'eis', 'sie', 'sei', 'ies', 'ise', 'esi', 'ei', 'ie', 'es'. 'se'. 'e'. 'i', 's'

kann mir jemand sagen, wie ich das anstellen koennte?
Auf die Schnelle mal zusammen gebastellt...
(funzt aber imho nicht mit doppelten Zeichen wie 'eise', daher auch die Prüfung mit "not .. in")

Code: Alles auswählen

def permut(lst=[],num=1,lst2=False):
    def _permut(lst1=[],lst2=False):
        lst=lst1
        if not lst2:
            temp = lst[:]
        else:
            temp = lst2[:]
        res=[]
        for i in xrange(0,len(lst),len(temp)):
            for j in xrange(0,len(temp)):
                temp.append(temp.pop(0))
                for k in xrange(0,len(temp)):
                    if not temp[k] in lst[i+k]: res += [lst[i+k] + temp[k]]
        return res

    res=lst[:]
    if not lst2:
        for i in xrange(1,num):
                res = _permut(res,lst)
    else:
        res = _permut(res,lst2)
    return res


###

li=list('1234')

res=permut(li,1)
print "1 Zeichen (%s):\n%s" %(len(res),res)
res=permut(li,2)
print "2 Zeichen (%s):\n%s" %(len(res),res)
res=permut(li,3)
print "3 Zeichen (%s):\n%s" %(len(res),res)
print "or"
res=permut(permut(permut(li,1,li),1,li),1,li)
print "4 Zeichen (%s):\n%s" %(len(res),res)

l=map(list,('1','12','123','1234','12345','123456','1234567','12345678'))
for i in l:
    print "Anzahlen fuer:",i
    for j in xrange(1,len(i)+1):
        print "%s : " %(len(permut(i,j))),

Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Freitag 31. Oktober 2008, 16:55

DasIch hat geschrieben:Wäre ein rekursiver Generator bei Permutationen nicht sinnvoller?
Wenn ich mich recht an mein Studium erinnere, ist Rekursion in etwas weniger Code zu implementieren, kann aber - besonders in Fällen wie diesen - deutlich mehr Ressourcen beanspruchen.
abgdf

Freitag 31. Oktober 2008, 16:56

PS: was meint ihr: wie lange wird ein rechner mit 2 GHz CPU fuer 14 zeichen brauchen
Also, wenn Du das wirklich immer noch machen willst, würde es sich glaube ich schon lohnen, das in C (wenn nicht in Assembler) anzugehen.

Vielleicht reicht das sogar immer noch nicht, dann bräuchte man Großrechner oder massive kollektive Rechenpower wie bei Seti@home

http://de.wikipedia.org/wiki/Verteiltes_Rechnen

Dann ginge das - vielleicht.

Gruß
abgdf

Freitag 31. Oktober 2008, 17:49

Hier

http://www.tutorials.de/forum/c-c/31323 ... ahlen.html

hat Thomas Darimont z.B. folgenden (von mir leicht ergänzten) C-Code gepostet:

Code: Alles auswählen

/* perm.c, compile with

   gcc -Wall -W -ansi -pedantic -O3 -o permutation perm.c

 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char *c, int firstIndex, int secondIndex);

void permut(char *c, int endIndex);
       
int main(void)
{
    char c[20];
    printf("Eingabe Wort: ");
    scanf("%s", c);
    fflush(stdin);
    permut(c, strlen(c) - 1);
    return (EXIT_SUCCESS);
}
       
void swap(char *c, int firstIndex, int secondIndex)
{
    char tmp = c[firstIndex];
    c[firstIndex] = c[secondIndex];
    c[secondIndex] = tmp;
}
       
void permut(char *c, int endIndex)
{
    int i;

    if(endIndex == 0)
    {
        puts(c);
    }
    else
    {
        permut(c, endIndex - 1);

        for(i = 0; i < endIndex; i++)
        {
            swap(c, i, endIndex);
            permut(c, endIndex - 1);
            swap(c, i, endIndex);
        }
    }
}
Dürfte schon etwas schneller sein. (Mit "e", "i" usw. müßte man nochmal gucken).

Viele Grüße
Antworten