β

Python计算笛卡尔积的两种方法

昔我往矣 41 阅读

cartesian-product

求笛卡尔积可能是最常用的集合操作了。

先说下场景,在项目中需要把中文姓名翻译成拼音,然后让用户选择正确转换的拼音存入数据库里,我使用了

pypinyin 这个Python库。。

简单是使用如下:

import pypinyin

res = pypinyin.pinyin('朴长落', style=pypinyin.STYLE_NORMAL, heteronym=True)
print(res)

会得到如下的结果

[['pu', 'po', 'piao'], ['zhang', 'chang'], ['luo', 'la', 'lao']]

需要把以上得到的拼音转成可阅读的拼音组合,例如 puzhangluo 。这所有可能的组合就是笛卡尔积,维基百科的定义如下:

在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,在集合论中表示为X × Y,是所有可能的有序对组成的集合,其中有序对的第一个对象是X的成员,第二个对象是Y的成员。

举个实例,如果集合X是13个元素的点数集合{ A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2 },而集合Y是4个元素的花色集合{♠, ♥, ♦, ♣},则这两个集合的笛卡儿积是有52个元素的标准扑克牌的集合{ (A, ♠), (K, ♠), ..., (2, ♠), (A, ♥), ..., (3, ♣), (2, ♣) }。

获取姓名拼音的所有组合,也就是求 笛卡尔积 。因为姓名长度可能是2个字、3个字和4个字或者更多,使用多层for循环显然是既丑又low的。我先后使用了两种方法来实现,一开始,我使用了Python的嵌套函数,使用深度搜索算法。后来才发现 Python 的 itertools库中自带了解 笛卡尔积 的计算方法。这里还是两个都写出来。

嵌套函数实现深度优先搜索算法

def solvemultinick(lst):
    ans = []

    def nicknamedfs(str, curIndex, alist):
        #global ans
        length = len(alist)
        if curIndex >= length:
            ans.append(str)
            return
        for item in alist[curIndex]:
            nicknamedfs(str + item, curIndex + 1, alist)
    nicknamedfs('', 0, lst)
    return ans

这个方法能够解决问题,但还是有点难读吧。就不解释代码了,建议大家使用下面的方法。

用itertools库实现的方法

import itertools

for i in itertools.product(*ans):
    print(''.join(i))

最后

Python的各个开源模块对于写Python来说简直就是一个宝库,难的是你要有能力去发掘,才能减少自己造轮子.针对上面 朴长落 的例子,1,2两种方法都能得到如下的结果.

puzhangluo
puzhangla
puzhanglao
puchangluo
puchangla
puchanglao
pozhangluo
pozhangla
pozhanglao
pochangluo
pochangla
pochanglao
piaozhangluo
piaozhangla
piaozhanglao
piaochangluo
piaochangla
piaochanglao
作者:昔我往矣
原文地址:Python计算笛卡尔积的两种方法, 感谢原作者分享。

发表评论