6

假设您在列表 L 中有一个字符串 S 和一个数字序列，使得 len(S) = len(L)。

检查是否可以找到字符串的字符与序列中的数字之间的双射，以使每个字符匹配一个且仅一个数字，最干净的方法是什么。

例如，“aabbcc”应与 115522 匹配，但不能与 123456 或 111111 匹配。

我有一个带有两个字典和循环的复杂设置，但我想知道是否有一种干净的方法可以做到这一点，也许是通过使用 Python 库中的一些函数。

4

5 回答 5

8

我会为此使用一组：

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(distinct2) == len(distinctMappings)

如果一个序列比另一个序列短，这也将返回 true，但已经建立了有效的映射。如果序列的长度必须相同，则应为此添加检查。

于 2012-11-21T08:30:26.597 回答
0

由于您通常只谈论集合之间的双射，因此我假设与其他答案不同，数字的顺序不必与字母的顺序相匹配。如果是这样，有一个简短而优雅的解决方案，但它需要collections.Counter在 python 2.7 中引入的类。对于那些坚持使用旧版本的人，有一个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))
于 2012-11-21T10:30:06.590 回答
0 
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
于 2012-11-21T08:43:51.090 回答
0

有一种更优雅的方法可以做到这一点（使用排序和itertools.groupby），但我现在很想睡觉，无法解决这个问题。但这应该仍然有效：

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

希望这可以帮助

于 2012-11-21T08:45:21.297 回答
0

这尊重顺序：

>>> 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
于 2012-11-21T08:49:52.517 回答