如何获得小于n的自然数互质子集的最大和? [英] How to get maximum sum of a coprime subset of naturals less than n?
问题描述
我需要一个函数来列出给定数字的较小互质数.例如，co(11) 给出 [1,7,9,10]，它的总和给我 27.但我想得到产生最大总和的互质数.对于 co(11)，它应该消除 10(因为 5+8 > 10)并返回 [1,5,7,8,9] 以获得最大和，即 30.这是函数:
I need a function which lists smaller co-prime numbers of given number. For example, co(11) gives [1,7,9,10], sum of it gives me 27. But i want to get co-prime numbers which generates maximum sum. For co(11) it should eliminate 10 (since 5+8 > 10) and return [1,5,7,8,9] to get maximum sum which is 30.
Here is the function:
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
为了得到可能的互质集合的最大和，它应该返回
In order to get maximum sum of possible co-prime sets, it should return
[1, 5, 7, 8, 9]
30
我想过获取所有可能的互质集合，然后比较它们以获得最大的总和.但是当 Co(N) 变大时，它变得不可控且效率低下.我知道这比 python 更像是数学问题，但任何提示都将不胜感激.
I thought about getting all possible co-prime sets then compare them to get the maximum summed one. But when the Co(N) gets bigger, it becomes uncontrollable and not efficient. I know this is more math problem than python but any hints would be appreciated.
推荐答案
回溯有效，但要处理大 n，您必须小心分支策略(我使用了 Bron-Kerbosch 算法与旋转用于枚举最大集团)并具有有效的修剪策略.我在开始时使用的修剪策略为图形着色(我使用了 以反向退化顺序的贪婪着色).为了计算对 Bron-Kerbosch 的特定递归调用的界限，将已经选择的节点 (R) 和每种颜色的最大节点相加，该颜色仍可能被选择 (P)，因为相同颜色的两个节点肯定不属于同一个集团.
Backtracking works, but to handle large n, you have to be careful about the branching strategy (I used the Bron–Kerbosch algorithm with pivoting for enumerating maximal cliques) and have an effective pruning strategy. The pruning strategy that I used colors the graph at the outset (I used a greedy coloring in reverse degeneracy order). To compute a bound for a particular recursive invocation of Bron–Kerbosch, add up the nodes already chosen (R) and for each color the maximum node of that color that may still be chosen (P), since two nodes of the same color definitely do not belong to the same clique.
在 Python 3 中:
In 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)
这篇关于如何获得小于n的自然数互质子集的最大和?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
