Tìm khả năng đánh dấu giữa các ký tự và chữ số

Question

Giả sử bạn có một chuỗi S và một chuỗi các chữ số trong danh sách L sao cho len (S) = len (L).

Điều gì sẽ là cách kiểm tra sạch nhất nếu bạn có thể tìm thấy một sự đánh dấu giữa các ký tự của chuỗi với các chữ số trong chuỗi sao cho mỗi ký tự khớp với một và chỉ một chữ số.

Ví dụ, "aabbcc" phải phù hợp với 115.522 nhưng không 123456 hoặc 111111.

Tôi có một thiết lập phức tạp với hai dicts và vòng lặp, nhưng tôi tự hỏi nếu có một cách sạch để làm điều này, có lẽ bằng cách sử dụng một số hàm từ thư viện Python.

Answer 1

tôi sẽ sử dụng một bộ cho việc này:

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

Tập thứ hai sẽ có chiều dài tương đương với tập đầu tiên khi và chỉ khi các bản đồ là surjective. (Nếu nó không phải là, bạn sẽ có hai bản sao của một ánh xạ thư cho cùng một số trong tập thứ hai, hoặc ngược lại)

Đây là mã mà thực hiện ý tưởng

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) 

này cũng sẽ trở lại đúng nếu một chuỗi ngắn hơn một trình tự khác, nhưng bản đồ hợp lệ đã được thiết lập. Nếu các chuỗi phải có cùng độ dài, bạn nên thêm dấu kiểm cho chuỗi đó.

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 

hay:

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

Có một cách thanh lịch hơn để làm điều này (với phân loại và itertools.groupby), nhưng tôi wayy ngủ-thành vô để con số đó ra ngay bây giờ. Nhưng điều này vẫn nên làm việc:

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 

Hope this helps

Answer 4

này tôn trọng trật tự:

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

Vì bạn thường chỉ nói về bijections giữa các bộ, tôi giả sử, không giống như những câu trả lời khác, rằng số thứ tự không cần khớp với thứ tự của các chữ cái. Nếu vậy, có một giải pháp ngắn, thanh lịch, nhưng nó đòi hỏi lớp collections.Counter, được giới thiệu trong python 2.7. Đối với những người bị mắc kẹt với một phiên bản cũ, có một backport for 2.5+.

from collections import Counter 

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

Thử nghiệm:

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

ví dụ của bạn là thay vì ánh sáng trên các trường hợp cạnh, bởi vì một cách khác để đọc câu hỏi của bạn cho phép số lượng chữ số và số lượng chữ là không công bằng (tức là bạn nhìn để đánh dấu từ tập hợp các ký tự duy nhất cho tập hợp các chữ số duy nhất, ví dụ: "aabbcc" sẽ phát sinh lên "123333".). Nếu đây là ý của bạn, hãy sử dụng phiên bản này thay thế:

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