Найти возможную биекцию между символами и цифрами

Question

Предположим, что у вас есть строка S и последовательность цифр в списке L такая, что len (S) = len (L).

Что было бы самым чистым способом проверки, если вы можете найти биекцию между символами строки и цифрами в последовательности, чтобы каждый символ соответствовал одной и только одной цифре.

Например, «AABBCC» должна соответствовать 115522, но не 123456 или 111111.

У меня есть сложная настройка с двумя dicts и петли, но мне интересно, если есть чистый способ сделать это, возможно, используя некоторую функцию из библиотек Python.

Answer 1

Я хотел бы использовать набор для этого:

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

Второго набор будет иметь длину, равную первый набор, если и только если отображение сюръективно. (Если это не так, вы будете иметь две копии отображения письма на тот же номер во втором наборе, или наоборот)

Вот код, который реализует идею

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) 

Это также будет возвращать true, если одна последовательность короче другой, но действительное сопоставление уже установлено. Если последовательности должны быть одинаковой длины, вы должны добавить чек для этого.

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 

или:

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

Там есть более элегантный способ сделать это (с сортировкой и itertools.groupby), но я wayy в сон-deproved, чтобы понять это прямо сейчас. Но это должно работать:

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 

Надеется, что это помогает

Answer 4

Это уважает порядок:

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

Поскольку обычно говорят только о биекциях между множествами, я полагаю, в отличии от других ответов, что заказ цифр не обязательно соответствует порядку букв. Если это так, есть короткое, изящное решение, но для него требуется класс collections.Counter, который был представлен на python 2.7. Для тех, кто придерживается старой версии, есть backport for 2.5+.

from collections import Counter 

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

Тестирование:

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

Ваши примеры достаточно свет на крайних случаях, потому что другой способ читать ваш вопрос позволяет количество цифр и количеству букв неравными (т.е. вы смотрите для биекции из набора уникальных символов в набор уникальных цифр, поэтому, например, "aabbcc" будет биектировать на "123333".). Если это то, что вы имели в виду, используйте эту версию:

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