Mögliche Kombinationen unter besonderen Umständen

[FidoroChun]

Ja der Titel sagt im Prinzip schon alles.
Bitte vermeidet solche Posts wie: "Wozu brauch man sowas?"

Also: Ich brauche eine Formel, mit der ich genau ausrechnen kann, wie viele mögliche Kombinationen es gibt. Als Input gibt es ein Wort wie hier dargestellt:

Code: Alles auswählen

x = raw_input("Bitte Wort eingeben").lower()

Die Kombinationen müssen (genau) alle Buchstaben von x enthalten.

Ich lasse die Kombinationen in einer Schleife erstellen, und würde nun gerne eine Abfrage schreiben, die die Schleife beendet, wenn die erstellten Kombinationen = die möglichen Kombinationen sind. Jedoch gibt es ja immer eine unterschiedliche Anzahl an Buchstaben.

Code: Alles auswählen

len(x)

habe ich ja...

Ich hoffe ihr versteht mein Dilämmer SuFu und lmgtfy habe ich schon versucht...
Dank im Voraus für eure Antworten.

[FidoroChun]

Achja,
hier das Script, falls ihr es für das Verstehen meines Problems benötigt (Ich kann ja leider nicht in eure Köpfe sehen, sonst hätte ich ja kein Problem )
http://www.python-forum.de/pastebin.php?mode=view&s=316
Bitte keine Kommis über das Script, ich mache meine Programme, wie ich es am besten kann

[EyDu]

Hallo und willkommen im Forum!

Was genau ist denn dein Ziel? Möchtest du nur die Anzahl der Kombinationen bestimmen oder willst du alle Kombinationen (als Liste von Wörtern) haben?

[BlackJack]

@FidoroChun: Keine Frage wozu man das braucht — Hausaufgaben!

Frag mal eine Suchmaschine Deiner Wahl nach den Begriffen Kombinationen und Permutationen. Und wenn Dir der Unterschied klar ist, überlege noch mal welches von beiden Du haben möchtest. Bei den Suchbegriffen sollten auch die entsprechenden Formeln unter den Suchergebnissen sein. Eventuell auch Algorithmen wie man die jeweils aufzählt.

Ausserdem solltest Du mal einen Blick in die Dokumentation des `itertools`-Moduls aus der Python-Standardbibliothek werfen, was es da für schöne, nützliche Funktionen gibt. Man muss ja nicht alles selber programmieren.

Der Quelltext sind nicht besonders gut aus.

[FidoroChun]

Hallo und willkommen im Forum!

Was genau ist denn dein Ziel? Möchtest du nur die Anzahl der Kombinationen bestimmen oder willst du alle Kombinationen (als Liste von Wörtern) haben?

Danke
Ich will alle Kombintionen als eine Liste von Wörtern haben, und dazu die mögliche Anzahl möglicher Kombinationen nutzen

[BlackJack]

@FidoroChun: Nein das möchtest Du nicht. Weder die Kombinationen noch mit *dem* Algorithmus. Das mit dem Zufall skaliert so überhaupt nicht, weil es je mehr Ergebnisse schon gefunden wurden, immer unwahrscheinlicher wird ein weiteres Ergebnis zufällig zu „treffen”. Man kann die Ergebnisse auch systematisch in linearer Zeit aufzählen. Oder aufzählen lassen. Lies Dir meinen letzten Beitrag noch einmal durch.

[derdon]

Bitte keine Kommis über das Script

Ich übersetze das mal zu "Bitte kein Feedback. Bitte keine Verbesserungsvorschläge." (korrigiere mich, wenn ich das falsch verstanden haben sollte). Warum bist du nicht offen für Kommentare von erfahrenen Leuten, die dir dabei weiterhelfen können, mit weniger Code, der dazu noch lesbarer ist, das gleiche zu tun oder noch mehr als in der Ursprungsversion?

[FidoroChun]

Bitte keine Kommis über das Script

Ich übersetze das mal zu "Bitte kein Feedback. Bitte keine Verbesserungsvorschläge." (korrigiere mich, wenn ich das falsch verstanden haben sollte). Warum bist du nicht offen für Kommentare von erfahrenen Leuten, die dir dabei weiterhelfen können, mit weniger Code, der dazu noch lesbarer ist, das gleiche zu tun oder noch mehr als in der Ursprungsversion?

Ja okay. Da haste natürlich Recht, aber ich habe immer Angst, dass ich gar nicht mehr mitkomme, wenn mich Profis belehren. Aber bitte korrigiert mich

[jerch]

@FidoroChun:
Gib doch mal ein Bsp-String und was Du haben möchtest, dann lässt sich auch Licht ins Permutation-vs-Kombinations-Dunkel bringen.

@BlackJack:
Ich glaube nicht, dass das Finden "fertiger" Funktionen Ziel der Hausaufgabe ist.

[EyDu]

@BlackJack:
Ich glaube nicht, dass das Finden "fertiger" Funktionen Ziel der Hausaufgabe ist.

Zum Testen der eigenen Ergebnisse ist es doch optimal.

[FidoroChun]

@BlackJack:
Ich glaube nicht, dass das Finden "fertiger" Funktionen Ziel der Hausaufgabe ist.

Zum Testen der eigenen Ergebnisse ist es doch optimal.

Nochmals: Es ist keine Hausaufgabe, in Informatik machen wir gerade ein 4 Gewinnt, und das hat damit rein gar nichts zu tun.

Okay, hier mal ein Beispiel:
hall
-> ahll
-> hlla
-> llah
-> lhal
-> lhla
-> llha
-> lahl
-> allh
-> lalh
-> alhl
-> hlal
... sind dann die möglichen "Kombinationen" oder wie es auch immer heißen mag. Das möchte ich erreichen.

[webspider]

Sieht nach Permutationen aus, deren Anzahl mittels n! (lies: Fakultät) berechnet werden kann. Was eigentlich jeder Informatikstudent schon im Mathekurs (bzw. jeder Schüler in den letzten paar Jahren) zumindest kurz behandelt haben sollte.

[jerch]

@webspider:
Nicht ganz, da die 'l's nicht unterscheidbar sind, ist es für hall 4!/2!

Simple Herangehensweise wäre, alle Permutationen zu suchen und Dopplungen rauszuschmeissen. Da gibt sicherlich was eleganteres.

[FidoroChun]

Okay, ich habe leider nicht viele fähige Lehrer, die mir sowas beibringen. Mein Informatiklehrer, weiß noch weniger als ich, und mein Mathelehrer ist mit uns noch nicht so weit leider.

[FidoroChun]

@webspider:
Nicht ganz, da die 'l's nicht unterscheidbar sind, ist es für hall 4!/2!

Simple Herangehensweise wäre, alle Permutationen zu suchen und Dopplungen rauszuschmeissen. Da gibt sicherlich was eleganteres.

Ich weiß, du bist nicht mein Mathelehrer, aber kannst du mir bitte kurz erklären, wie du auf diese Gleichung kommst?

[BlackJack]

@jerch: Im Programm steht was von Anagramm, also sind die zwei kleinen L's doch unterscheidbar.

Edit: Ist natürlich Blödsinn.

[jerch]

@FidoroChun:
Kein Ding, die Gleichung ergibt sich wie folgt:

1) Die Permutationen von n Elementen erhältst Du mit n!. Das kannst Du Dir selbst überlegen, wenn Du Dir vergegenwärtigst, dass Du n Elemente nur auf n * (n-1) * ... * 1 Weise anordnen kannst.
2) Hast Du gleiche Elemente, gibts Dopplungen, die nicht unterscheidbar sind. Die berechnest Du auf gleiche Weise: bei einem Doppelelement -> 2!, einem Tripel -> 3! usw. Treten mehrere auf, multiplizierst Du die Fakultäten, zB. eine Dopplung und ein Tripel -> 2! * 3!

Diese Mehrfachelemente reduzieren die Anzahl unterscheidbarer Anordnungen aus 1), ergo teilst Du 1) durch 2)

Bsp: walhalla

1) Permutationen: 8!
2) Gruppen: 3 * 'a' und 3 * 'l' --> 3! * 3!
---> 8! / (3! * 3!)

Damit erhältst Du die Gesamtanzahl möglicher unterscheidbarer Anordnungen von walhalla.

[BlackJack]

Ein bisschen Quelltext dazu:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8
from itertools import groupby, imap, permutations
from math import factorial


class Anagrams(object):
    def __init__(self, text):
        self._text = sorted(c for c in text.lower() if c.isalpha())
    
    def __len__(self):
        result = factorial(len(self._text))
        for _, group in groupby(self._text):
            result /= factorial(sum(1 for _ in group))
        return result
    
    def __iter__(self):
        seen = set()
        for anagram in imap(''.join, permutations(self._text)):
            if anagram not in seen:
                seen.add(anagram)
                yield anagram


def main():
    anagrams = Anagrams(raw_input('Text eingeben: '))
    for anagram in anagrams:
        print anagram
    print 'Das waren %d Anagramme.' % len(anagrams)


if __name__ == '__main__':
    main()

[FidoroChun]

@ BlackJack
Vielen Dank. Das hilft mir weiter

Ich werde das mal probieren, wenn ich wieder zuhause bin.

[StefanLawl]

Tut mir Leid, dass ich jetzt total am Thema vorbeischieße, aber ...

Bitte keine Kommis über das Script, ich mache meine Programme, wie ich es am besten kann

Programmierer programmieren um zu lernen, wenn du keine Kommentare hören willst, wie willst du dann was lernen?

Ich widersetze mich einfach mal und schreibe einen kurzen Kommentar zu deinem Skript

Code: Alles auswählen

    erste_combination = ""
    for i in get_t():
        erste_combination = erste_combination + i.upper()
    list_anagrams.append(erste_combination)

Wenn ich das richtig verstehe (habe es nicht ausprobiert) möchtest du aus einer Liste ein groß geschriebenes Wort erstellen. Eine Liste kannst du mit ''.join(liste) zu einem String "verwandeln". Jetzt müsste man es nur noch mit str.upper() kapitalisieren (kann man das so aus dem Englischen capitalize übersetzen? )

Code: Alles auswählen

>>> list = ['h','a','i','t','h','a','r']
>>> ''.join(list).upper()
'HAITHAR'

Python ist so eine wunderschöne Sprache, weil es viel Arbeit durch builtin Funktionen und Bibliotheken abnimmt, mach dich ein bisschen mit ihnen vertraut

Des weiteren kannst du dir Objektorientierung ansehen, ist handlicher. Generell ist "global" keine schöne Lösung (habe ich auch gelernt, wurde mir gesagt )

Wehre dich nicht gegen Kritik und Kommentare, nur so lernt man Und "ich mache es, wie ich es am besten kann" ist nicht wirklich die beste Einstellung, wenn es darum geht, Programme effizient und "schön" zu programmieren.

Stefan