Monoalphabetische Kombination

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.
Antworten
Quicktrader
User
Beiträge: 16
Registriert: Freitag 6. November 2015, 20:24

Hi..

es gibt ja die wunderbare Zeilen

Code: Alles auswählen

alphabet = ['a', 'b', 'c']
import re
for x, y, z in [(x,y,z) for x in alphabet for y in alphabet for z in alphabet]:
	chain = x+y+z
	print (chain)
was an und für sich ja gut funktioniert und

Code: Alles auswählen

abc acb bac bca...
hervorbringt, korrekterweise aber leider auch

Code: Alles auswählen

aaa abb bbc...
Nun würde ich gerne davon ausgehen, dass jeder Buchstabe höchstens einmal in einem Ergebnis ('chain') verwendet werden kann, d.h. wurde für x bereits 'a' gewählt, so soll für y nur noch 'b' bzw. 'c' in Frage kommen. Dies jedoch nicht grundsätzlich, denn in der nächsten Ergebniszeile soll durchaus wieder für y der Buchstabe 'a' möglich sein, dann jedoch für x bzw. z eben nur noch 'b' bzw. 'c'.

Mathematisch liegt der Unterschied wohl bei 3^3 = 9 Kombinationen versus 3! = 3x2x1 = 6 Kombinationen, der Rechenaufwand ist also erheblich geringer.

Leider kann ich jedoch in die 're'-Funktion nicht eingreifen (Super-Newbie) und auch ein vorgelagertes

Code: Alles auswählen

a != b
oder

Code: Alles auswählen

a is not b
hatte bedauerlicherweise keine Auswirkung auf die 're'-Funktion. Diese ist ja auch zurecht darauf ausgelegt, für jede Variable jeden Wert aus 'der Liste ('alphabet') zu verwenden.

Kennt jemand eine alternative Möglichkeit, die strings in allen Variationen - allerdings anhand von Variablen (x,y,z) - ohne doppelte Werte miteinander zu kombinieren?

Bzw. einen Zusatz, welcher dies im Zuge der 're'-Funktion ermöglicht?

Code: Alles auswählen

for x, y, z in [(x,y,z) for x in alphabet for y in alphabet for z in alphabet] and a != b:
bleibt nämlich (ohne 'h') ebenfalls ohne Wirkung bzw. führt zu einem Boole-Fehler #sigh#.

Die Variablen erscheinen mir erforderlich, da in weiterer Folge ja die Verkettung ('chain') folgen soll. Vielen Dank für Eure Unterstützung,

Quicktrader
Zuletzt geändert von Anonymous am Montag 13. März 2017, 13:09, insgesamt 5-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
Sirius3
User
Beiträge: 17737
Registriert: Sonntag 21. Oktober 2012, 17:20

@Quicktrader: schau Dir mal die Funktionen im Modul `itertools` an.
Quicktrader
User
Beiträge: 16
Registriert: Freitag 6. November 2015, 20:24

SIrius3, danke für den Tipp, ich würde es demnach mit permutations probieren, befürchte jedoch dass ich dann das Ergebnis

['abc', 'bca',..]

erhalte anstatt

abc
bca

Dass ich jedoch im Grunde die Variablen und nicht die Listenwerte permutieren wollte, hat mich glaube ich ursprünglich von der Permutation zur 're'-Funktion gebracht (not iterable usw...)..aber ich werd's nochmal probieren.

QT
BlackJack

@Quicktrader: Ich verstehe das Ziel nicht und bin auch extrem verwirrt darüber das Du das `re`-Modul importierst und ständig etwas von einer `re`-Funktion erzählst → was soll das sein?

Und was ist der Unterschied zwischen ['abc', 'bca',..] und

abc
bca

Ausser das das eine eine Liste ist und das andere wie Ausgabe der einzelnen Zeichenketten aus der Liste?
Quicktrader
User
Beiträge: 16
Registriert: Freitag 6. November 2015, 20:24

Hallo, danke der Nachfrage. Man kann es sich so vorstellen:

Man bilde eine Kette namens 'chain' und unterscheidet das uns bekannte Alphabet in häufige, mittel häufige und weniger häufige Buchstaben:

Code: Alles auswählen

chain = VAR1 + VAR2 + VAR3 + VAR4 + VAR5

mit 

VAR1 aus alphabet_häufig
VAR2 aus alphabet_mittel
VAR3 aus alphabet_wenigerhäufig
VAR4 aus alphabet_häufig
VAR5 aus alphabet_mittel
Nun würde ich gerne alle kombinatorischen Varianten sehen, ohne dass z.B. VAR1 und VAR4 beide den alphabetischen Buchstaben 'E' repräsentieren. Beide Variablen greifen jedoch auf die Gruppe 'alphabet_häufig' zu (also z.B. die häufigen Buchstaben ETAOINSRH).

['abc', 'bca',..] hilft nicht weiter da es wohl eine Liste, eine Kombination von Buchstaben darstellt und nicht eine Kombination von Variablen. Das bedeutet ich hätte dann fälschlicherweise alle Kombinationen von VAR1, also z.B. alle Kombinationen häufiger Buchstaben permutiert (ETAOINSRH, ETAOINSHR, usw.). Ich suche jedoch alle kombinatorischen Varianten der 'chain', d.h. alle möglichen Werte von VAR1 mit allen möglichen Werten von VAR2 usw. miteinander kombiniert - jedoch ohne dass VAR1 = VAR2 möglich ist!

In der eingangs genannten Funktion

Code: Alles auswählen

for x, y, z in [(x,y,z) for x in alphabet for y in alphabet for z in alphabet]:
    chain = x+y+z
    print (chain)
wäre die Kombination zunächst leicht möglich, da man bestimmen kann ob x aus 'alphabet' oder z.B. aus 'alphabet_häufig' oder 'alphabet_wenigerhäufig' usw. gewählt werden darf.

In diesem 'case' wären alle Werte wunderbar miteinander in der 'chain' kombiniert und stünden zur weiteren Auswertung zur Verfügung. Und zwar noch nicht einmal als strings, wie dies bei einer einfachen Permutation der Fall wäre (die ja auch nur innerhalb einer Gruppe funktioniert..hier haben wir aber drei Permutationen die zu dem string-Ergebnis vieler chains führen sollen..).

Allerdings will ich eben nun tunlichst vermeiden, dass VAR1 und VAR4 innerhalb eines chain-Teilergebnisses DENSELBEN Wert zugewiesen bekommen, selbst wenn beide Variablen auf die gleiche Gruppe von häufigen Buchstaben ('alphabet_häufig') zugreifen. Der alphabetische Buchstabe 'E' soll also z.B. in einer 'chain' bzw. einem chain-Teilergebnis höchstens einmal vorkommen können. Dies, je nach kombinatorischem Fortschritt, entweder auf Position VAR1 oder auf Position VAR2 oder sogar überhaupt nicht (wenn z.B. VAR1 = 'A' und VAR4 = 'T' in der chain aufscheint und somit das Teilergebnis chain(n) eben kein 'E' beinhaltet).

Bei Zahlen wäre dies aliquot

Code: Alles auswählen

for VAR1 in range(0,6) for VAR4 in range (0,6) usw...
Auch hier wäre das Problem gegeben, dass VAR1 und VAR2 gegebenenfalls beide denselben Wert, z.B. 0, zugewiesen bekommen (weil nunmal beide aus dem selben Range Bereich beziehen. Dass aber beide nicht 0 sein sollen, wäre eine gewünschte Nebenbedingung, z.B. zwecks Vermeidung eines mathematischen 0x0 Werts bzw. anderer Potenzen (z.B. 3x3).

Eine Lösung unter der Nebenbedingung, dass Var1 nicht gleich Var4 sein darf, ist mir bisher leider noch nicht geglückt.

Quicktrader
Sirius3
User
Beiträge: 17737
Registriert: Sonntag 21. Oktober 2012, 17:20

@Quicktrader: so ganz verstehe ich Dein Problem noch nicht. Du sprichst von Gruppen mit verschieden häufigen Buchstaben. Aus dem Beispiel sehe ich, dass Du zwei disjunkte Buchstaben aus Gruppe häufig, zwei aus mittel und einen aus wenigerhäufig haben willst.
Du mußt also mehrstufig vorgehen: Jeweils alle Permutationen ohne Wiederholung für zwei Buchstaben einer Gruppe in eine Liste schreiben und dann alle Kombinationen dieser drei Listen durchgehen.

Die restlichen Beispiele sind wenig hilfreich, da Du dort nur mit einer Gruppe an Buchstaben arbeitest, Dein eigentliches Problem also gar nicht auftritt.
jerch
User
Beiträge: 1669
Registriert: Mittwoch 4. März 2009, 14:19

@Quicktrader:
Deine Problembeschreibung ist iwie nur schwer nachzuvollziehen. Suchst Du etwas in der Art?

Code: Alles auswählen

from itertools import product, starmap, ifilter

haeufig = 'abc'
selten = 'def'

def chain(a, b, c, d):
    if a != c and b != d:
        return a + b + c + d
    return None

for result in ifilter(bool, starmap(chain, product(haeufig, selten, haeufig, selten))):
    print result
Im Prinzip ist das einfach Dein erstes Bsp. etwas umgeschrieben. `product` selbst ist kombinatorisch der worst case mit der größten Ergebnismenge, allerdings auch sehr viel einfacher zu berechnen als z.B. eine Permutation, da der Einzelschritt ein einfacher Schleifendurchlauf ist. Daher Obacht, das wächst mit vielen Verkettungen böse an (exp). Ggf. musst Du Vorberechnungen mit Teilbereichen erstellen, um die Ergebnismenge nicht zu sehr anwachsen zu lassen.
Quicktrader
User
Beiträge: 16
Registriert: Freitag 6. November 2015, 20:24

@Sirius3

vielen Dank zunächst, Dein Ansatz, disjunkt schon bei der Permutation genau die Anzahl an Werten auszuwählen die ich insgesamt in der 'chain' benötige, hat mir sehr weitergeholfen (!geniuscredits!). Problematisch wird dies jedoch, wenn sich die alphabetischen Bereiche überlappen (was bei mir leider der Fall ist, 'Bereiche' sozusagen):

Code: Alles auswählen

alphabet_häufig = ['E', 'T', 'A', 'O']
alphabet_mittel = ['O', 'I', 'N', 'S']
alphabet_selten = ['S', 'R', 'H', 'D']
Unbekannt ist, ob die drei häufigsten 'Repräsentanten' nun gesichert für ETA oder vielleicht doch für ETO oder TAO oder OTA etc. stehen. In der 'chain' kann somit auch bei disjunkter Permutation der Gruppe 'alphabet_häufig' bei zwei verschiedenen Variablen der Wert 'O' aufscheinen. In vorgenanntem Beispiel sogar bei VAR1, VAR2, VAR5, was eben genau zu Ungleichheiten und Unmengen an überflüssigem und irritierenden Rechenaufwand führt. Bis zu drei 'O' wären in der kurzen chain mit nur fünf Buchstaben möglich, so auch mit dem in zwei Gruppen vorhandenen Buchstaben 'S' (und hier im Beispiel habe ich nur jeweils einen Buchstaben, welcher überlappt..in real sind es 5-6 je Gruppe..).

Ansonsten wäre Dein Ansatz schon die Lösung..bitte um Nachsicht dass ich die Überlappung nicht schon eingangs erwähnt habe. Wenn das noch gelöst wäre: Satz an die Decke...

LG
Quicktrader
User
Beiträge: 16
Registriert: Freitag 6. November 2015, 20:24

Ok, die Lösung steht..danke nochmal an Sirius3 bzgl. disjunkter Permutation.

Auf "from itertools import *" anstatt "import itertools" wäre ich als Laie ebenfalls nicht so ohne weiteres gekommen..desweiteren sollten die Werte noch entsprechend aus der Liste ausgelesen werden bzw. die Anzahl benötigter Buchstaben bereits vorab in der Permutation angegeben werden. Um eine Verwechslung mit dem Alphabet zu vermeiden, habe ich die originären 'Zeichen' (wir sprechen über eine simple Subsitution) als rr2, rr3 usw. angegeben.

Die aus der Permutation 'gezogenen' Klartextbuchstaben werden dann der Reihe nach auf die ursprünglichen Zeichen verteilt, so kann in weiterer Folge eine Kette gebildet werden (chain)..diese wird bei mir in weiterer Folge mit einem Aho-Corasick-Algorithmus ausgewertet. Vorab sind selbstverständlich noch die Variablen zu definieren (z.B. 'rr2 = 0' bzw. chain = rr2+ll3.. usw). Es sei angemerkt, dass es wesentlich aufwändigere Methoden zur Darstellung einer monoalphabetischen Substitution gibt (z.B. http://practicalcryptography.com/crypta ... ar-cipher/).

Danke nochmal an alle Beteiligten.

QT

Code: Alles auswählen

from itertools import *
for t in permutations(["A", "O", "I", "N", "S", "R", "H", "L", "D", "C"],3): ## Häufige Buchstaben, benötigte Anzahl 'chain'
    for m in permutations (["R", "H", "L", "D", "C", "U", "M", "F", "P", "G", "W"],7): ## Mittelhäufige Buchstaben..
        for l in permutations (["F", "P", "G", "W", "Y", "B", "K", "X", "Q", "Z"],3): ## Weniger häufige..
            rr2 = l[0]
            ll3 = m[0]
            ru2 = t[0]
            rr3 = t[1]
            rr1 = l[1]
            uu2 = t[2]
            oo1 = m[1]
            lu1 = m[2]
            ro2 = m[3]
            ru3 = m[4]
            lo1 = m[5]
            ru1 = m[6]
            uu3 = l[2]
            chain = rr2+ll3+ru2+rr3+rr1+uu2+oo1+rr3+lu1+ro2+ru3+lo2+lo1+ru1+lo2+uu3+lo2+lo2+uu2+ll3+ll3+lo2+ru1+ro1+ro2+ro1
            >>> weitere Auswertung
        
Ergebnis sieht dann z.B. so aus

FRAOPIHOLDCEUMEGEEIRREMTDT
FRAOPIHOLDCEUMEWEEIRREMTDT
FRAOPIHOLDCEUMEYEEIRREMTDT
FRAOPIHOLDCEUMEBEEIRREMTDT
FRAOPIHOLDCEUMEKEEIRREMTDT
FRAOPIHOLDCEUMEXEEIRREMTDT
FRAOPIHOLDCEUMEQEEIRREMTDT
FRAOPIHOLDCEUMEZEEIRREMTDT
FRAOGIHOLDCEUMEPEEIRREMTDT
FRAOGIHOLDCEUMEWEEIRREMTDT

(Kein Zeichen verwendet irgendeinen Buchstaben aus seiner (!) Gruppe doppelt).
Antworten