118. 全数字素数集合(Pandigital prime sets)

使用1至9的全部数字，并自由连接起来组成十进制整数，可以构造不同的集合。其中一个集合\(\{2,5,47,89,631\}\)非常有趣，因为它的所有元素都是素数。有些集合包含数字1至9恰好各一次，且所有元素都是素数，这样的集合有多少个？

分析：我解决这道题的思路是这样的：首先把\(\{1,2,3\cdots,9\}\)这九个数字构成的集合进行分割，这个在数学上一般称为\(set\ partition\)，划分的方式可以使用贝尔数求得共有\(21147\)种。接下来，对于每一种划分方式，我们要考虑其中每个子集的不同排列，因为不同排列会对应不同的数字。比如说其中一种划分方式为\(\{[2],[5],[4,7],[8,9],[6,3,1]\}\)，则除开一位数以外，我们需要它们的不同排列，如\([4,7]\)即可以是47也可以74，\([6,3,1]\)既可以是631也可以163。只有当某一种分割方式下构成的数字都是质数时，才符合题目的要求。需要注意的是，每个子集可形成不同排列，而一个划分会有多个子集，则最终形成的不同数字组成方式为这些子体的不同排列的笛卡尔乘积。

我们可以使用\(sympy\)中的\(multiset\_partition()\)函数来进行集合分割，使用\(permutations()\)函数来计算子集的不同排列，使用\(product()\)函数计算笛卡尔乘积，再使用\(isprime()\)函数判断数字是否是质数。因为使用了几个外部库，代码比较简短，但在运行时间应该还有优化的空间。代码如下：

# time cost = 10.4 s ± 291 ms

from itertools import permutations,product
from sympy import isprime
from sympy.utilities.iterables import multiset_partitions

def main():
    cnt = 0
    for pt in multiset_partitions([str(x) for x in range(1,10)]):
        for perm in product(*(permutations(x) for x in pt)):
            if all(isprime(int("".join(x))) for x in perm):
                cnt += 1
    return cnt