如何枚举泛数字素数集

Question

欧拉计划第 118 题写道：“使用 1 到 9 的所有数字并将它们自由连接形成十进制整数，可以形成不同的集合。有趣的是，集合 {2,5,47,89,631} 的所有元素都属于它是素数。有多少个包含数字 1 到 9 中的每个数字恰好一次的不同集合仅包含素数元素。”

这是我迄今为止遇到的唯一一个没有提供问题的简单版本答案的问题。结果，我很难检查我所做的算法。你看出可能是什么问题了吗？

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

首先，我生成所有相关素数的列表。这是每个具有 9 个或更少数字的素数，没有重复的数字，并且没有 0 作为其数字之一。然后我使用这个列表创建一个集合计数字典。该字典的键是冻结集，表示每个素数具有哪些数字，值是整数，用于计算减少到该集合的相关素数的数量：

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

显然我的方法有缺陷。

Answer 1

缺陷是这样的。考虑集合

{2,5,47,89,631}

。不同的初始分裂可能会导致它。一个是

{1,2,3,6}, {4,5,7,8,9}

，另一个是

{1,3,6,8,9} {2,4,5,7}

。还有更多。因此你多算了。

为了让您享受这个问题的乐趣，我不会告诉您如何解决这个计数过多的问题。我只是告诉你，如果你计算到达特定集合的多种方式，那么你的数字就会太高了。