alle möglichen Länge k-Kombinationen einer string in python

Ich würde gerne alle möglichen Kombinationen der Buchstaben in einem string mit der Länge k. Ich weiß es gibt viele Beiträge zu diesem Thema, aber ich habe ein wenig verdrehen, k ist größer als die Länge der Zeichenfolge.

Dies ist, was ich habe, so weit, seine einfach, und es funktioniert, wenn k <= len(string):

 string = 'ABCD'
 permutations = ["".join(x) for x in itertools.permutations(string, k)]

Ergebnisse, wenn k = 4:

 ['ABCD', 'ABDC', 'ACBD', 'ACDB', 'ADBC', 'ADCB', 'BACD', 'BADC', 'BCAD', 'BCDA', 
'BDAC','BDCA', 'CABD', 'CADB', 'CBAD', 'CBDA', 'CDAB', 'CDBA', 'DABC', 'DACB', 
'DBAC', 'DBCA', 'DCAB', 'DCBA']

Diese wie erwartet funktioniert. Ich möchte jedoch alle möglichen Kombinationen dieser vier Buchstaben, mit k > len(string).

Beispiel Antwort, die ich gerne sein würde:

string = 'AB'
k = 4
result = ['AAA,'ABB','AAB', 'ABA','BBB', 'BAA'.......]

Vielen Dank im Voraus.

  • Es gibt 4^15 strings der Länge 15, bestehend aus A, B, C und D. Das sind über eine Milliarde - strings. Natürlich Ihr computer verklemmt sich. (Beachten Sie, dass es gibt eine Billion Permutationen von 15 Elementen, das ist, was Sie gebeten, Ihren computer zu berechnen)
  • Sie sollten ein Beispiel geben von dem, was die Ausgabe, die Sie sehen wollen.
  • rechten, Weg, SO kann eingeklemmt werden bis zu verarbeiten versucht eine multi-GB HTTP POST, anstatt nur die Fragesteller die computer verklemmt sich 😉
  • Ich bin mir relativ sicher, dass so ein POST fehlschlagen würde. Zumindest hoffe ich so. (plötzlicher Drang zu versuchen)
  • Beachten Sie, dass itertools.permutations ist, geben Sie die Anzahl der gut.... Permutationen, Kombinationen nicht. Nachdem, was @nneonneo sagte, wenn Sie erlauben wiederholten Buchstaben m^n möglichen strings der Länge n, mit m Symbolen. Gegeben ein string s der Länge n, gibt es n! (Fakultät) Permutationen von s. Eine permutation ist eine Neuordnung, die verwendet jeder der ursprünglichen Elemente nur einmal.
  • Ok ja, das ist der Grund, warum es verklemmt sich Sinn macht. Sorry ich bin sehr neu in der Programmierung. Eine andere Möglichkeit wäre, um nicht zu speichern und alle Kombinationen. Ich bin versucht, suchen eine sehr große string für die Anzahl der vorkommen jeder Kombination und sehen, welche Kombination tritt am häufigsten auf.
  • Dann bitten. Don ' T fallen in die Falle des X/Y-problem. (Wenn Sie tatsächlich überprüfen Sie jede einzelne Kombination, Ihr Speicher und CPU-Zeit explodieren. Es gibt viel, viel einfachere Wege).
  • Das Beispiel, das Sie Gaben mit 'AB' und k = 4 nicht der gleichen Logik Folgen wie die, die Sie gab mit 'ABCD' und k = 4. Ich finde das irreführend. Ich blieb mit der Auslegung der letzteren zu bauen, meine Antwort.
  • Ihre Beispiele scheinen nicht zu entsprechen. Sie haben 'AAA' im Beispiel am Ende, aber Sie haben nicht 'AAAA' in der Ausgabe vom permutations - code, den Sie sagen, ist richtig.

InformationsquelleAutor Samantha | 2013-10-17
  1. 8

    Möchten Sie möglicherweise

    itertools.product(string, repeat=k)

    statt. Probieren Sie es aus! Deine Beschreibung ist unzureichend definiert, so nicht erraten können, das ist sicher.

    Beispiel:

    >>> import itertools
>>> for p in itertools.product("ab", repeat=3):
...     print p
('a', 'a', 'a')
('a', 'a', 'b')
('a', 'b', 'a')
('a', 'b', 'b')
('b', 'a', 'a')
('b', 'a', 'b')
('b', 'b', 'a')
('b', 'b', 'b')
    • Und sich auch bewusst sein, dass Sie wahrscheinlich nicht über genügend Speicher, um in der Lage sein, um eine Liste aus dieser für k=15. Aber das ist OK, der Punkt der itertools zum Teil ist das generieren von Sequenzen, die zu groß für den Speicher.
    InformationsquelleAutor Tim Peters
  2. 3

    Basierend auf Ihren Kommentar:

    Ich versuche, Suche einen sehr großen string für die Anzahl der vorkommen jeder Kombination und sehen, welche Kombination tritt am häufigsten auf.

    Gibt es eine andere Möglichkeit, das zu tun, was Sie wollen:

    def substrings(vlarge, k):
    return (vlarge[idx:idx+k] for idx in range(len(vlarge)-k+1))

def uses_only(value, chars):
    return all(ch in chars for ch in value)

def most_common(vlarge, chars, k):
    return collections.Counter(s for s in substrings(vlarge, k) if uses_only(s, chars)).most_common(1)

    Können Sie sich dann zu machen, diese grundlegende Idee effizienter: zum Beispiel, wenn Sie Begegnung ein 'x' Charakter in vlarge dann wissen Sie, dass keiner von den Teilstrings gehören, die es werden Kombinationen von 'abcd'. So können Sie überspringen der substring beginnt, dass ein Ort nach dem x:

    def generate_substrings(vlarge, chars, k):
    idx = 0
    goodrange = 0
    while idx <= len(vlarge) - k:
        while goodrange < idx + k:
            if vlarge[goodrange] in chars:
                goodrange += 1
            else:
                idx = goodrange + 1
                if idx > len(vlarge) - k:
                    return
                goodrange = idx
        yield vlarge[idx:goodrange]
        idx += 1

def most_common(vlarge, chars, k):
    return collections.Counter(generate_substrings(vlarge, chars, k)).most_common(1)

    Verglichen mit diesem Ansatz, der "offensichtlich" Idee (iterieren über alle Kombinationen, zu zählen, wie oft Sie erscheinen als ein substring, und verfolgen Sie den besten bisher) weniger Speicher verbraucht wird aber eine viel langsamer, da es sich um viel der Pässe über die sehr große string.

    Wenn ich falsch verstanden habe was du meinst mit "Kombinationen", das heißt, wenn mein uses_only - Funktion falsch ist, dann müsstest du die Lautstärke meiner Vorstellung entsprechend. Der Punkt ist: die Zahl der tatsächlichen Teilzeichenketten der form, die Sie wollen, da gibt es weniger von Ihnen gibt als hypothetische Teilstrings der richtigen form.

    InformationsquelleAutor Steve Jessop
  3. 1

    Meine Antwort nur eine theoretische Analyse von dem, was Sie tun.
    Ich bezeichne die binomial-Koeffizienten definieren die Anzahl der Teile mit k Elemente einer Reihe mit n Elemente von C(k,n).

    Angenommen, Sie haben einen string der Länge n ∈ zahlen ℕ* und k ∈ zahlen ℕ, k ⩾ n. Ich werde annehmen, dass alle Zeichen im string sind deutlich.

    Ich habe verstanden, dass Sie versuchen, erstellen Sie eine Zeichenfolge von k Zeichen extrahiert aus Ihrem input-string.

    Eine Kombination aus string Zeichen gesehen werden kann als eine permutation ⟦1, n⟧. Es gibt n! solche Permutationen ...

    Dann, wenn k > n, sind die Dinge immer viel schlimmer ... Lass r = k mod n und p = (k - r)/n. Offensichtlich haben wir :

    p ⩾ 1

    0 ⩽ r < p

    Ihre Ausgabe-string kann es zerlegt werden in p "komplette" Teilzeichenfolgen aus einer permutation von Ihrem n Zeichen eingeben, und einen substring aus nur r Zeichen der Eingabezeichenfolge.

    So bauen Sie einen "unvollständigen" substring, müssen Sie zuerst wählen Sie eine Teilmenge von r Zeichen der Eingabe-Zeichenfolge und dann eine permutation von solchen Charakteren. Endlich, die Reihe sr,n, um mögliche unterfolgen :

    sr,n = C(r,n).r!

    Beachten Sie, dass diese Formel führt nicht zu einer ungültigen Globale Ergebnis, wenn r = 0, da C(0,n) = 1 und 0! = 1 per Konvention.

    Die endgültige Zahl der k-lange strings können Sie bauen nach Ihren Schema :

    stot = (C(r,n).r!).(n!)p

    Diese Zahl ist unverschämt hoch !

    Mit k = 4 und n = 2 haben wir :

    stot = (C(0,4).0!).(2!)2 = 4

    result = ['ABAB', 'ABBA', 'BAAB', 'BABA']
    InformationsquelleAutor Rerito
Schreibe einen Kommentar