如何获取小于n的互质自然数子集的最大总和？

Question

我需要一个函数，它可以列出给定数字的更小的互质数。例如，co(11)得到[1,7,9,10]，其和为27。但是我想要获得生成最大总和的互质数。对于co（11），它应该消除10（因为5+8 > 10），并返回[1,5,7,8,9]以获得最大总和，即30。 以下是函数：

import math
def Co(n):
    Mylist = [x for x in range(1, n)]
    removeds  =[]
    for x in Mylist:
        y = Mylist.index(x)
        for z in Mylist[y+1:]:
            if math.gcd(x, z) != 1:
                removed = Mylist.pop(y)
                removeds.append(removed)
                #print(removed)
                Mylist[1:] = Mylist
                #print(Mylist)
                break
    
    Mylist= list(dict.fromkeys(Mylist))
    removeds = list(dict.fromkeys(removeds))
    removeds.sort(reverse = True)
    for a in removeds:
        check = []
        for b in Mylist:
           if math.gcd(a, b) != 1:
               break
           else:
               check.append(a)
        if len(check) == len(Mylist):
           Mylist.append(a)
           
      
    print(Mylist)
    print(sum(Mylist))
Co(11)

结果如下：

[1, 7, 9, 10]
27

为了获取可能的互质集合的最大和，应该返回：

[1, 5, 7, 8, 9]
30

我考虑获取所有可能的互质集合，然后进行比较以获得最大的总和。但当 Co(N) 变得更大时，它变得难以控制且效率低下。我知道这更多是数学问题而不是 python 问题，但任何提示将不胜感激。

- fatih arslan

Answer 1

回溯法可以解决问题，但是为了处理大规模的 n，你需要仔细考虑分支策略（我使用了 Bron-Kerbosch 算法与枢轴 枚举最大团）并采用有效的剪枝策略。我使用的剪枝策略在一开始对图进行染色（我使用了 反向退化顺序贪心染色）。为了计算 Bron-Kerbosch 的特定递归调用的上界，将已选择的节点（R）相加，并对于每个颜色选择可能仍然被选择的最大节点（P），因为同一颜色的两个节点肯定不属于同一个团。

Python 3 中：

import math


def coprime_graph(n):
    return {
        i: {j for j in range(1, n) if j != i and math.gcd(j, i) == 1}
        for i in range(1, n)
    }


def degeneracy_order(g):
    g = {v: g_v.copy() for (v, g_v) in g.items()}
    order = []
    while g:
        v, g_v = min(g.items(), key=lambda item: len(item[1]))
        for w in g_v:
            g[w].remove(v)
        del g[v]
        order.append(v)
    return order


def least_non_element(s):
    s = set(s)
    i = 0
    while i in s:
        i += 1
    return i


def degeneracy_coloring(g):
    coloring = {}
    for v in reversed(degeneracy_order(g)):
        coloring[v] = least_non_element(coloring.get(w) for w in g[v])
    return coloring


def max_cliques(g, coloring, bound, r, p, x):
    if not p and not x:
        yield r

    best = {}
    for v in p:
        i = coloring[v]
        if v > best.get(i, 0):
            best[i] = v
    if sum(r) + sum(best.values()) <= bound[0]:
        return

    u_opt = min(p | x, key=lambda u: len(p - g[u]))
    for v in sorted(p - g[u_opt], reverse=True):
        p.remove(v)
        yield from max_cliques(g, coloring, bound, r | {v}, p & g[v], x & g[v])
        x.add(v)


def max_sum_clique(g):
    coloring = degeneracy_coloring(g)
    bound = [0]
    best_so_far = set()
    for clique in max_cliques(g, coloring, bound, set(), set(g), set()):
        objective = sum(clique)
        if objective > bound[0]:
            bound[0] = objective
            best_so_far = clique
    return best_so_far


def main(n):
    print(max_sum_clique(coprime_graph(n)))


if __name__ == "__main__":
    main(500)

- David Eisenstat

---

感谢您的解释和努力，有很多东西需要理解。但是当我尝试 main(30) 时，它返回目前为止最好的 {1, 2, 5, 7, 9}，实际上这并不是最佳的结果。我是否对整个函数有什么误解？ - fatih arslan

@fatiharslan修复了一个bug - 我在max_cliques中迭代了错误的顶点集v。 - David Eisenstat

非常感谢。我觉得我至少需要一周的时间来理解这段代码是做什么的 :) - fatih arslan

很好 :) - CristiFati

测试到450，结果集中的所有数字最多只有两个质因数，这可能会导致更高效的算法。我想知道是否有一种方法可以证明对于更大的数字也是如此。 - גלעד ברקן

Answer 2

我并没有真正查看您的代码，但我认为它不能按预期工作，因为一旦在解决方案中添加了一个符合条件的元素，它就不会回头（搜索更好的替代方案），所以您会陷入第一种解决方案。
有许多方法可以解决这类问题，我将使用回溯法。

关于此方法的几点说明：

• 很简单（在我的观点中）
• 生成所有可能的解决方案（这可能是它的优点，但也可能是它的缺点）
• 高度低效（对于我们的问题），通常是暴力等效方法。 对于更高的n值，时间复杂度将呈指数增长

此外，回溯法可以以多种形式实现，我选择了递归形式。

code00.py:

#!/usr/bin/env python

import sys
from math import gcd


def is_valid(item, arr):
    for elem in arr:
        if gcd(elem, item) > 1:
            return False
    return True


def bt(n, sols, cur_sol):
    if cur_sol:
        sols.add(tuple(cur_sol))
    for i in range(cur_sol[-1] + 1 if cur_sol else 1, n):
        if is_valid(i, cur_sol):
            cur_sol.append(i)
            bt(n, sols, cur_sol)
    else:
        if cur_sol:
            cur_sol.pop()


def main(*argv):
    solutions = set()
    current_solution = []
    n = 11
    start_time = time.time()
    bt(n, solutions, current_solution)
    end_time = time.time()
    print("Solutions:", sorted(solutions))
    print("\nFor n={0:d}, it took {1:.6f} seconds".format(n, end_time - start_time))
    best_solution = max(solutions, key=sum)
    print("\nBest solution: {0:}\nSum: {1:}".format(best_solution, sum(best_solution)))


if __name__ == "__main__":
    print("Python {0:s} {1:d}bit on {2:s}\n".format(" ".join(elem.strip() for elem in sys.version.split("\n")), 64 if sys.maxsize > 0x100000000 else 32, sys.platform))
    main(*sys.argv[1:])
    print("\nDone.")

输出:

[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q065062781]> "e:\Work\Dev\VEnvs\py_pc064_03.07.06_test0\Scripts\python.exe" code00.py
Python 3.7.6 (tags/v3.7.6:43364a7ae0, Dec 19 2019, 00:42:30) [MSC v.1916 64 bit (AMD64)] 64bit on win32

Solutions: [(1,), (1, 2), (1, 2, 3), (1, 2, 3, 5), (1, 2, 3, 5, 7), (1, 2, 3, 7), (1, 2, 5), (1, 2, 5, 7), (1, 2, 5, 7, 9), (1, 2, 5, 9), (1, 2, 7), (1, 2, 7, 9), (1, 2, 9), (1, 3), (1, 3, 4), (1, 3, 4, 5), (1, 3, 4, 5, 7), (1, 3, 4, 7), (1, 3, 5), (1, 3, 5, 7), (1, 3, 5, 7, 8), (1, 3, 5, 8), (1, 3, 7), (1, 3, 7, 8), (1, 3, 7, 10), (1, 3, 8), (1, 3, 10), (1, 4), (1, 4, 5), (1, 4, 5, 7), (1, 4, 5, 7, 9), (1, 4, 5, 9), (1, 4, 7), (1, 4, 7, 9), (1, 4, 9), (1, 5), (1, 5, 6), (1, 5, 6, 7), (1, 5, 7), (1, 5, 7, 8), (1, 5, 7, 8, 9), (1, 5, 7, 9), (1, 5, 8), (1, 5, 8, 9), (1, 5, 9), (1, 6), (1, 6, 7), (1, 7), (1, 7, 8), (1, 7, 8, 9), (1, 7, 9), (1, 7, 9, 10), (1, 7, 10), (1, 8), (1, 8, 9), (1, 9), (1, 9, 10), (1, 10), (2,), (2, 3), (2, 3, 5), (2, 3, 5, 7), (2, 3, 7), (2, 5), (2, 5, 7), (2, 5, 7, 9), (2, 5, 9), (2, 7), (2, 7, 9), (2, 9), (3,), (3, 4), (3, 4, 5), (3, 4, 5, 7), (3, 4, 7), (3, 5), (3, 5, 7), (3, 5, 7, 8), (3, 5, 8), (3, 7), (3, 7, 8), (3, 7, 10), (3, 8), (3, 10), (4,), (4, 5), (4, 5, 7), (4, 5, 7, 9), (4, 5, 9), (4, 7), (4, 7, 9), (4, 9), (5,), (5, 6), (5, 6, 7), (5, 7), (5, 7, 8), (5, 7, 8, 9), (5, 7, 9), (5, 8), (5, 8, 9), (5, 9), (6,), (6, 7), (7,), (7, 8), (7, 8, 9), (7, 9), (7, 9, 10), (7, 10), (8,), (8, 9), (9,), (9, 10), (10,)]

For n=11, it took 0.000000 seconds

Best solution: (1, 5, 7, 8, 9)
Sum: 30

Done.

- CristiFati

---

谢谢你的回答。这正是我所想的，但我无法弄清楚如何在Python中实现它。但是当N变得更大时，这种解决方案就会失败。例如，当你给n=100时，它需要永远才能返回结果。 - fatih arslan

嗯，那是真的。显然这不是正确的方法。 - CristiFati

但请记住，我认为没有一种方法适用于任何n。那么预期的max n是多少（以及预期的时间是多少）？ - CristiFati

实际上，max n 是 200000，时间并不是很重要。 - fatih arslan