logo标签列表

将一组数字分成两组，使得其中一组的数字与另一组的数字没有任何公共因数

pythonalgorithmmath
7
我需要将一组数字分成两组，使得一组中的任何数字的因子都不是另一组中任何数字的因子。我认为我们只需要找到这样的组，使得每个组中数字的乘积的最大公约数为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. 除法后，矩阵如下所示-

enter image description here

  1. 组=(2,4,6),(3,6,9),(5),(7)
  2. 合并后的组=(2,3,4,6,9),(5),(7)
  3. 最后，组合很容易，因为我只需要知道这些可以组合的方式总数。
我认为这个算法可以工作，但是这是一种非常糟糕的方法来解决这个问题。如果元素数量达到10E6或更多，我可以硬编码素数直到一个大数字，然后找到最接近我的最大数字的素数，这可能会使它更快，但是仍然涉及太多除法。也许有更好的方法来解决这个问题。也许是我遗漏了某些数学公式，或者有一些小技巧可以减少迭代次数。
我的问题是关于算法的，伪代码也可以，我不需要完整的代码。然而，我熟悉Python、Fortran、C、BASH和Octave，因此这些语言中的答案也会有所帮助，但是正如我所说，语言不是关键点。如果有必要，可以帮我修改措辞，让我的问题更好。
不仅仅是质数。让我们考虑数字集合（5、6、8、9）。6和8不是质数。因此，我们可以形成像{(5,6,8)(9) , (5,6)(8,9), (5),(6,8,9) .. }这样的分组。 - Ashraff Ali Wahab
1
(5,6,8)(9)不是一个有效的组合，因为3是在第一组中的数字6的因子，也是在第二组中的数字9的因子。我的问题明确说明了任何一组中任何数字的因子不能与另一组中任何数字的因子相同。 - Yuki.kuroshita
2
第一句话的意思是“第一组中没有一个数字有一个因子，该因子也是第二组中任何数字的因子”。6和8都有因子2，所以它们必须在同一组中。如果我错了，请纠正我。 - bjschoenfeld
@brandon，是的，你说得对，可以看看我上面的评论。 - Yuki.kuroshita
2个回答
7

tl;dr: 使用素数筛选获取质数列表，使用并查集存储和组合节点

方法

你已经在正确的方向上了。您可以使用 Eratosthenes 筛法 来获取质数列表，并且您只需要 ~O(n log n) 的时间和内存来进行质因数分解，这并不算太糟糕。

让我们稍微转换一下问题的后半部分：

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

现在你需要找到两个不相交的节点组。将这些组存储在并查集中。

示例

您的示例略有缩短，使用元素 [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方法，以返回该子集元素的Python set形式的质因数。为了节省空间，只有父节点应包含此属性。
def get_prime_factors(x):
    return Find(x)._prime_factors
  1. 修改 union 方法，返回对新集合的引用，并跟踪其素数因子（即 set 的交集）。
def union(x, y):
    # use Wikpidia's code
    # ...

    # add this:
    xRoot._prime_factors |= yRoot._prime_factors
    return xRoot
  1. 定义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)。

1
我一直觉得我制作的矩阵可以转换成某种邻接矩阵，但我无法找出它们之间的关系。谢谢你的答案。 - Yuki.kuroshita
1
这是一种非常冗长的方法... 如果数字交换，您可能还会遇到答案重复的问题。
from functools import reduce
from itertools import combinations, chain
import copy

def factors(n):    
    return [x for x in set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) if x != 1]

#this creates a dictionary with the factors as keys and every element of the value list that it is a factor of
#{'2': [2, 4, 6], '3': [3, 6, 9], '4': [4], '5': [5], '6': [6], '7': [7], '9': [9]}
def create_factor_dict(values):
    factor_dict = {}
    for val in values:
        if len(factors(val)) != 0:
            for fac in factors(val):
                if str(fac) in list(factor_dict.keys()):
                    factor_dict[str(fac)] = factor_dict[str(fac)] + [val]
                else:
                    factor_dict[str(fac)] = [val]

    return factor_dict

#this deletes all the factor keys that appear as factor values of another key
#{'2': [2, 4, 6], '3': [3, 6, 9], '4': [4], '5': [5], '6': [6], '7': [7], '9': [9]} --> {'2': [2, 4, 6], '3': [3, 6, 9], '5': [5], '7': [7]}
def delete_duplicates(a_dict):
    for key in list(a_dict.keys()):
        check = copy.deepcopy(a_dict)
        del check[key]
        if int(key) in list(chain.from_iterable(list(check.values()))):
            del a_dict[key]
    return a_dict

#this merges values into groups if they contain common values
#{'2': [2, 4, 6], '3': [3, 6, 9], '5': [5], '7': [7]} -- > [[7], [5], [2, 3, 4, 6, 9]]
def merge_groups(a_dict):
    a_dict = delete_duplicates(a_dict)
    for key in a_dict:
        values = a_dict[key]
        for key2 in [x for x in list(a_dict.keys()) if x != key]:
            if True in [True for x in values if x in a_dict[key2]]:
                a_dict[key] = list(set(a_dict[key] + a_dict[key2]))
    groups = [list(i) for i in set(map(tuple, list(a_dict.values())))]
    return groups

#creates all pairs of 2 then merges into one group
#[[7], [5], [2, 3, 4, 6, 9]] ---> [[7, 5], [7, 2, 3, 4, 6, 9], [5, 2, 3, 4, 6, 9]]
def create_groups(a_dict):
    groups = merge_groups(a_dict)
    groups = [list(chain.from_iterable(x)) for x in list(combinations(groups, 2))]
    return groups




values = [2, 3, 4, 5, 6, 7, 8, 9]               
groups = create_groups(create_factor_dict(values))

#this finds the elements of value that do not appear in each group (that's the complimentary pair)
pairs = []
for x in groups:
    pair = []
    for v in values:
        if v in x:
            pass
        else:
            pair.append(v)
    pairs.append((x, pair))
print(pairs)

它输出：
[([7, 5], [2, 3, 4, 6, 8, 9]), ([7, 2, 3, 4, 6, 8, 9], [5]), ([5, 2, 3, 4, 6, 8, 9], [7])]
这不是我想到的吗？ - Yuki.kuroshita
@Yuki.kuroshita，我稍微改了一下你放置在矩阵中并分配0或1的部分，并使用字典方法创建更大的可组合组- 减少了迭代次数。 - Anna Nevison
1
是的，我注意到了。我选择使用不相交集合，但还是感谢你的回答。 - Yuki.kuroshita
@Yuki.kuroshita 我也会选择那个答案 - 那个其他的回答很棒，但感谢你的支持。 - Anna Nevison
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接