python - 将数字列表分成两组，使得一组中的数字与另一组中的数字没有任何共同因素

Question

我必须将一个数字列表分成两组，这样一组中没有一个数字的因数也是第二组中任何数字的因数。我认为我们然后只需要找出组，使得每组中数字乘积的 GCD 为 1。例如-

如果我们有列表 2,3,4,5,6,7,9 可能的组是 -

(2,3,4,6,9)(5,7)(2,3,4,5,6,9)(7)(2,3,4,6,7,9)(5)

我最初想做的是——

1. 生成一个素数列表，直到列表中的最大数量。
2. 将列表中的所有元素逐一除以每个素数，如果数字不能被素数整除，则将 0 分配给列表，如果可以整除，则将其分配给 1。
3. 对所有素数重复此操作，得到一个由 0 和 1 组成的矩阵。
4. 从第一个素数开始，将所有为1的元素归为一组。
5. 如果两个组具有相同的元素，则将这些组合并为一个组。
6. 计算这些组可以组合的可能方式的数量，我们就完成了。

从前面的例子来看，算法看起来像这样 -

1. 素数列表 = [2,3,5,7]
2. 除法之后，矩阵看起来像这样-

1. 组=(2,4,6),(3,6,9),(5),(7)
2. 加入的组=(2,3,4,6,9),(5),(7)
3. 最后，加入是简单的部分，因为我只需要这些可以组合的方式的数量。

我认为此算法可行，但它是解决此问题的一种非常糟糕的方法。我可以对素数进行硬编码直到一个很大的数字，然后找到最接近我的最大数字的素数，这可能会使它更快，但如果元素的数量是 10E6 或更多的数量级，它仍然涉及太多的除法。我在想也许有更好的方法来解决这个问题。也许我遗漏了一些数学公式，或者一些可以减少迭代次数的小逻辑。

我的问题是关于算法的，所以伪代码也可以，我不需要完成的代码。但是，我对 Python、Fortran、C、BASH 和 Octave 很满意，所以用这些语言回答也会有所帮助，但正如我所说，语言不是这里的重点。

而且我想我可能不知道一些可能会使我的问题变得更好的术语，因此也感谢您提供任何改写方面的帮助。

Answer 1

tl;dr:使用素数筛选法获取素数列表，使用不相交集存储和组合组

方法

您走在正确的轨道上。您可以使用 Sieve of Erasthones得到素数列表，你只需要 ~O(n log n) 时间和内存来分解素数，这还不错。

让我们稍微重构问题的后半部分:

• 原始列表中的每个数字都是图中的一个节点
• 如果数字有一个公因数，则两个节点之间有一条边

现在您的问题是找到两个不相交的节点组。将这些组存储在 disjoint set 中.

例子

您的示例的略短版本，包含元素 [2,3,4,5,6]。让我们跟踪子集列中的每组节点，并遍历上面的数组。

| iteration | subsets         | subset1 | description                                                                                                             |
|-----------|-----------------|---------|-------------------------------------------------------------------------------------------------------------------------|
| start     | []              | n/a     |                                                                                                                         |
| 1         | []              | {2}     | add a new subset, 2                                                                                                     |
| 2         | [{2}]           | {3}     | 3 shares no common factors with 2, so create a new subset 2                                                             |
| 3         | [{2},{3}]       | {4}     | 4 shares a common factor with 2, but not with 3, so merge it with {2}                                                   |
| 4         | [{2,4},{3}]     | {5}     | 5 shares no common factors with 2,3 or 4, so create a new subset                                                        |
| 5         | [{2,4},{3},{5}] | {6}     | 6 shares a common factor with {2,4}, so merge it into that.  it also shares a common factor with {3}, so merge that too |
| 6         | [{2,4,3,6},{5}] |         | done                                                                                                                    |   

方法

从具有标准属性 make_set、union 和 find 方法的不相交集开始，如 Wikipedia 中所述。

1. 使用 get_prime_factors 对其进行扩充，返回该子集元素的主要因子的 Python 集，以提高空间效率，只有父节点应包含此属性

def get_prime_factors(x):
    return Find(x)._prime_factors

1. 修改 union 以返回对新创建的集合的引用并跟踪素数因子(集合交集)

def union(x, y):
    # use Wikpidia's code
    # ...

    # add this:
    xRoot._prime_factors |= yRoot._prime_factors
    return xRoot

1. 定义 get_subsets()，这是一种迭代子集的方法。天真的方法是遍历原始数组并在每个数组上运行 find。不太天真的方法是用另一组来跟踪 parent ，但这种选择不会影响最坏情况下的运行时间。

代码

disjoint_set = AugmentedDisjointSet([])
elems = [2,3,6,5,4]

for new_number in elems:
    subset1 = disjoint_set.make_set(new_number)

    for subset2 in disjoint_set.get_subsets():
        if (subset1.get_prime_factors() & subset2.get_prime_factors()): # merge if the subsets share a common factor
            subset1 = disjoint_set.union(subset1, subset2)

# show result. this may give between 1 (all numbers share a common factor) 
# and infinite subsets (all numbers are relatively prime)
# for your example, this will return something like {2,3,4,6,9}, {5}, {7}
# you can group them however you'd like to.
print('result': disjoint_set.get_subsets())  

分析

最坏情况在 O(n^2*a(n)) 时间内运行，其中 a(n) 是反阿克曼函数(即非常小)，如果每个元素都是互质的，并且 O(n) 空间。