将数字列表分为两组，以便一组中的数字与另一组中的数字没有任何共同的因素

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. 对所有素数重复此操作，从而得到零和一的矩阵。
4. 从第一个素数开始，将所有具有1的元素放入一组。
5. 如果两个组具有相同的元素，则将这些组合并为一个组。
6. 计算可以组合这些组的可能方法的数量，我们完成了。

在前面的示例中，算法看起来像这样-

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

3. 组=（2,4,6），（3,6,9），（5），（7）
4. 已加入的组=（2,3,4,6,9），（5），（7）
5. 最后，加入是容易的部分，因为我只需要几种可以组合的方式即可。

我认为该算法有效，但是是解决此问题的非常不好的方法。我可以将素数硬编码为一个大数，然后找到最接近我的最大数的素数，这可能会使其更快，但是如果元素的数量约为10E6或更多，它仍然涉及过多的除法。我在想也许有更好的方法来解决这个问题。也许我缺少一些数学公式，或者一些可以减少迭代次数的小逻辑。

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

而且我想我可能不了解一些可能会使我的问题变得更好的术语，因此也希望对重新措词有所帮助。

Answer 1

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

方法

您走在正确的轨道上。您可以使用Erasthones的Sieve来获取质数列表，并且只需要~O(n log n)时间和内存即可进行质因数分解，这还不错。

让我们重新构造问题的后半部分：

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

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

例

示例的简短版本，带有elements [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方法如维基百科上所述。

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

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

2. 修改union以返回对新创建集合的引用，并跟踪主要因子（集合交集）

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

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

3. define get_subsets()，一种迭代子集的方式。天真的方法是遍历原始数组并find在每个数组上运行。较不幼稚的方法是跟踪另一组父母，但这种选择不会影响最坏情况下的运行时间。

码

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)空间。