Python 如何列举Pandigital Prime Set

欧拉项目118写道:"使用所有数字1到9并将它们自由地连接形成小数，可以形成不同的集合.有趣的是，对于集合{2，5，47，89，631}，属于它的所有元素都是素的.有多少个不同的集合包含一到九中的每个数字恰好一次只包含素元素？"

这是迄今为止我遇到的唯一一个无法提供更简单版本的问题.因此，我很难判断我所做的算法.你知道可能有什么问题吗？

我编写了一种非常简单的动态编程方法.为此，我将回答这个问题:"有多少个不同的集合恰好一次包含S中的每个数字仅包含素元素"，针对不同的S值，然后结合它们的结果来回答原始问题.

首先，我生成所有相关Prime的列表.这是每个数字数为9或更少的Prime，没有重复的数字，并且其中一个数字没有0.然后我使用此列表创建一个集计数字典.该字典的键是冻结集，表示每个Prime具有哪些数字，值是计算缩减到该集的相关Prime数量的数字的数字:

from itertools import chain, combinations
from functools import cache
from collections import defaultdict
from pyprimesieve import primes


primes = [
    p for p in primes(10**9) if len(set(str(p))) == len(str(p)) and "0" not in str(p)
]
set_counts = defaultdict(int)
for p in primes:
    set_counts[frozenset(map(int, str(p)))] += 1

set_counts然后将作为我们的回归的基本情况.

接下来，我们需要一种方法将我们的问题分解为相关的子问题.所以我写了一个函数，它将生成将集合拆分为两个不相交的非空子集的所有方法:

@cache
def set_decomps(s):
    """
    Generates all possible ways to partition a set s
        into two non-empty subsets
    """
    l = list(
        map(
            lambda x: (frozenset(x), s - frozenset(x)),
            chain.from_iterable(combinations(s, r) for r in range(1, len(s))),
        )
    )
    return l[: len(l) // 2]

最后，我们应该能够使用一种简单的记忆方法来一起使用这些来解决问题及其所有子变体.

@cache
def dp(s):
    """
    Returns the number of ways to create a set containing prime numbers
    Such that the set of all the digits in the primes is equal to s
    With no duplicates or extra digits
    """
    base = set_counts[s]
    if len(s) > 1:
        for a, b in set_decomps(s):
            base += dp(a) * dp(b)
    return base
print(dp(frozenset(range(1,10)))) # prints 114566, which is wrong

显然我的方法有一个缺陷.