查找字符和數字之間可能的雙射

Question

假設您有一個字符串S和一個列表L中的數字序列，使得len（S）= len（L）。

檢查是否可以在字符串中的字符與序列中的數字之間找到雙射，以便每個字符與唯一的一個數字相匹配，最乾淨的方法是什麼？

例如，「爲aabbcc」應與115522而不是123456或111111

我有兩個類型的字典和迴路複雜的設置，但我不知道是否有這樣做的清潔方式，也許通過使用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

既然你通常只說說集之間的雙射，我想，不像其他的答案，數字的訂單不需要匹配字母的順序。如果是這樣，有一個簡短而優雅的解決方案，但它需要python 2.7中引入的collections.Counter類。對於那些使用舊版本的用戶，有一個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))