6

len（S）= len（L）のように、リストLに文字列Sと一連の数字があるとします。

文字列の文字とシーケンス内の数字との間に全単射があり、各文字が1桁だけに一致するかどうかを確認する最もクリーンな方法は何でしょうか。

たとえば、「aabbcc」は115522と一致する必要がありますが、123456または111111とは一致しません。

2つのdictとループを含む複雑なセットアップがありますが、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)])

マッピングが全射である場合に限り、2番目のセットの長さは最初のセットと等しくなります。（そうでない場合は、2番目のセットの同じ番号にマッピングされた文字のコピーが2つあります。その逆も同様です）

これがアイデアを実装するコードです

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

これを行うためのよりエレガントな方法がありますが（並べ替えと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 に答える
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

通常は集合間の全単射についてのみ話すので、他の答えとは異なり、数字の順序は文字の順序と一致する必要はないと思います。もしそうなら、短くてエレガントな解決策がありますが、collections.Counterそれはpython2.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 に答える