有限集、图像和有限函数原像的惯用 Python 实现？

Question

假设我在有限集之间有一个有限具体函数。当然，Python 已经在本地实现了集合。

但是，准确地实现集合之间的有限函数的想法的最佳方式是什么？包装好的字典？另外，如何实现图像和原像的计算？ [见下文。]

对于图像我可以使用地图，很清楚。对于原像，我可以遍历域集和过滤器。尽管如此，我还是想知道更多 pythonic 惯用的解决方案。

Answer 1

对于从一组到另一组的任意图像，我会使用 Python 字典。比如一组{1,2,3,4}上的f(n)=n^2，我可以这样做：

preimage = set([1,2,3,4])
mapping = {x: x*x for x in preimage}
image = set(mapping.values())
assert set(mapping.keys()) == preimage
function = lambda x: mapping[x] # so you can now have y = function(x)
check_image = set([function(x) for x in preimage])
assert check_image == image

当然，这仅在您的有限集相对于您拥有的内存确实是有限的情况下才有效。

以上是将函数定义为映射的最常见情况。但是如果你可以用 Python 表达式来表示更简单的函数，你可以跳过字典：

preimage = set([1,2,3,4])
function = lambda x: x*x
image = set([function(x) for x in preimage])
check_preimage = set([y for x in image for y in preimage if function(y)==x])
assert check_preimage == preimage

如果更进一步，您有一个可用于域的反函数：

import math
preimage = set([1,2,3,4])
function = lambda x: x*x
inv_func = lambda x: int(math.sqrt(x))
image = set([function(x) for x in preimage])
check_preimage = set([inv_func(x) for x in image])
assert check_preimage == preimage

请注意，上面三个不同的代码片段，只有第一个可以保证您的 function(x) 只允许预定义原像中的那些 x。

说到惯用语 python：我不认为 Python 真的是一种数学语言（与 Wolfram 的 mathematica 相比）所以我们没有图像的概念，映射等内置。但是，您可以通过列表理解看到我上面的代码。事实上，我只是让事情更明确地使用 set 关键字，如 set([function(x) for x in preimage])，但你可以使用 {function(x) for x in preimage}.

节省一些击键

Answer 2

def preimage(b: B, f: Dict[A, B]) -> Set[A]: 
    ''' get the preimage of one item. '''
    return set(a for a in f.keys() if f[a]==b)

这假设 TypeVar and other things from pep484

from typing import TypeVar, Dict, Set
A = TypeVar('A')
B = TypeVar('B')

没有类型注释它看起来像这样

def preimage(b, f): 
  ...

或密码域的子集

from typing import Collection
from functools import reduce

def preimage_(bs: Collection[B], f: Dict[A, B]) -> Set[A]: 
    ''' get the preimage of a collection of items '''
    return reduce(lambda a, b: a.union(b), [preimage(b, f) for b in bs])

有限集、图像和有限函数原像的惯用 Python 实现？

Idiomatic Python implementation for finite sets, images, and preimages of finite functions?

python

discrete-mathematics