Finden Sie mögliche Bijektion zwischen Zeichen und Ziffern

Question

Nehmen wir an, Sie haben eine Zeichenfolge S und eine Folge von Ziffern in einer Liste L, so dass len (S) = len (L).

Was wäre die sauberste Art zu überprüfen, ob Sie eine Bijektion zwischen den Zeichen der Zeichenfolge zu den Ziffern in der Sequenz finden können, so dass jedes Zeichen zu einer einzigen Ziffer passt.

Zum Beispiel: „aabbcc“ sollte mit 115522 passen, aber nicht 123456 oder 111111

Ich habe einen komplexen Aufbau mit zwei dicts und Schleife, aber ich frage mich, ob es eine saubere Art und Weise ist, dies zu tun, vielleicht indem Sie eine Funktion aus den Python-Bibliotheken verwenden.

Answer 1

würde ich einen Satz für diesen Einsatz:

In [9]: set("aabbcc") 
Out[9]: set(['a', 'c', 'b']) 

In [10]: set(zip("aabbcc", [1, 1, 5, 5, 2, 2])) 
Out[10]: set([('a', 1), ('c', 2), ('b', 5)]) 

Der zweite Satz Länge gleich den ersten Satz erhalten wird, wenn und nur wenn die Zuordnung surjektiv ist. (Wenn dies nicht der Fall, werden Sie zwei Kopien einer Buchstabenzuordnung auf die gleiche Anzahl in dem zweiten Satz haben, oder umgekehrt)

Hier ist Code, der die Idee implementiert

def is_bijection(seq1, seq2): 
    distinct1 = set(seq1) 
    distinct2 = set(seq2) 
    distinctMappings = set(zip(seq1, seq2)) 
    return len(distinct1) == len(distinctMappings) and len(distinct2) == len(distinctMappings) 

Dies auch zurückkehren true, wenn eine Sequenz kürzer ist als die andere, aber eine gültige Zuordnung wurde bereits erstellt. Wenn die Sequenzen die gleiche Länge haben müssen, sollten Sie einen Check hinzufügen.

Answer 2

import itertools 

a = 'aabbcc' 
b = 112233 

z = sorted(zip(str(a), str(b))) 
x = all(
    gx == g0 
    for k, g in itertools.groupby(z, key=lambda x: x[0]) 
    for gx in g for g0 in g 
) 
print x 

oder:

import itertools 

a = 'aabbcc' 
b = 112233 

z = zip(str(a), str(b)) 
x = all(
    (z1[0] == z2[0]) == (z1[1] == z2[1]) for z1 in z for z2 in z 
) 
print x 

Answer 3

Es gibt einen eleganteren Weg, dies zu tun (mit Sortier- und itertools.groupby), aber ich bin wayy in den Schlaf-deproved, dass gerade jetzt, um herauszufinden. Dies soll aber immer noch funktionieren:

In [172]: S = "aabbcc" 

In [173]: L = [1, 1, 5, 5, 2, 2] 

In [174]: mapping = collections.defaultdict(list) 

In [175]: reverseMapping = collections.defaultdict(list) 

In [176]: for digit, char in zip(L, S): 
    mapping[digit].append(char) 
    reverseMapping[char].append(digit) 
    .....:  

In [177]: all(len(set(v))==1 for v in mapping.values()) and all(len(set(v))==1 for v in reverseMapping.values()) 
Out[177]: True 

In [181]: S = "aabbcc" 

In [182]: L = [1, 2, 3, 4, 5, 6] 

In [183]: mapping = collections.defaultdict(list) 

In [184]: reverseMapping = collections.defaultdict(list) 

In [185]: for digit, char in zip(L, S):                   
    mapping[digit].append(char) 
    reverseMapping[char].append(digit) 
    .....:  

In [186]: all(len(set(v))==1 for v in mapping.values()) and all(len(set(v))==1 for v in reverseMapping.values()) 
Out[186]: False 

this helps

Answer 4

Dies respektiert die Reihenfolge:

>>> s = "aabbcc" 
>>> n = 115522 
>>> l1 = dict(zip(s, str(n))).items() 
>>> l2 = zip(s, str(n)) 
>>> l1 
[('a', '1'), ('c', '2'), ('b', '5')] 
>>> l2 
[('a', '1'), ('a', '1'), ('b', '5'), ('b', '5'), ('c', '2'), ('c', '2')] 
>>> not bool([i for i in l2 if i not in l1]) 
True 
>>> n = 115225 
>>> l1 = dict(zip(s, str(n))).items() 
>>> l2 = zip(s, str(n)) 
>>> not bool([i for i in l2 if i not in l1]) 
False 

Answer 5

Da Sie in der Regel nur über Bijektionen zwischen den Sätzen sprechen, nehme ich an, im Gegensatz zu den anderen Antworten, dass die Bestellung der Ziffern nicht der Reihenfolge der Buchstaben entsprechen muss. Wenn ja, gibt es eine kurze, elegante Lösung, aber es erfordert die Klasse collections.Counter, die in Python 2.7 eingeführt wurde. Für diejenigen, die mit einer älteren Version stecken, gibt es eine backport for 2.5+.

from collections import Counter 

def bijection_exists_between(a, b): 
    return sorted(Counter(a).values()) == sorted(Counter(b).values()) 

Testing:

>>> bijection_exists_between("aabbcc", "123123") 
True 
>>> bijection_exists_between("aabbcc", "123124") 
False 

Ihre Beispiele sind eher leicht an den Rand Fällen, weil ein anderer Weg, um Ihre Frage zu lesen, für die Anzahl der Ziffern und die Anzahl der Buchstaben können ungleich sein (dh Sie suchen für eine Bijektion von der Menge der eindeutigen Zeichen zu der Menge der eindeutigen Ziffern, so würde z. B. "aabbcc" auf "123333" verweisen.). Wenn das ist, was Sie meinten, verwenden Sie stattdessen diese Version:

def bijection_exists_between(a, b): 
    return len(set(a)) == len(set(b))