alle kombinationen von zeichen in einem string

[roschi]

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

[numerix]

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?

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]

Vielleicht kannst Du auch die Stellen der Buchstaben in Zahlen umwandeln und dann mit "random.shuffle()" arbeiten. Natürlich nicht bei 14 Zeichen ...

[EyDu]

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

Code: Alles auswählen

\sum_{i=1}^{14}\binom{14}{i}14^i = 29.192.926.025.390.624

[abgdf]

Ich glaube, das Problem ist mathematisch nicht so ganz leicht:

http://www.daniweb.com/code/snippet459.html
http://procrastinationrising.com/2007/0 ... on-python/

Gruß

[numerix]

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

[numerix]

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

[roschi]

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?

[Y0Gi]

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]

@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]

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]

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]

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]

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]

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

[abgdf]

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

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]

(die Funktion "permut" ruft sich dauernd selbst auf ):

Das nennt sich Rekursion.

[yipyip]

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!

yipyip

[Leonidas]

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

[DasIch]

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