我想要做什么:
我需要创建一个函数,给定一个正整数列表(可以有重复的整数),计算所有三元组(列表中),其中第三个数字是第二个数字的倍数,第二个数字是第一个数字的倍数:
(同一个数字不能在一个三元组中使用两次,但可以被所有其他三元组使用)
例如,[3, 6, 18]
是一因为18
均匀地进入6
均匀地进入3
.
所以给出[1, 2, 3, 4, 5, 6]
它应该找到:
[1, 2, 4] [1, 2, 6] [1, 3, 6]
并返回3
(找到的三元组的数量)
我尝试过的:
我做了几个可以工作但效率不够的函数。是否有一些我不知道的数学概念可以帮助我更快地找到这些三元组?具有更好功能的模块?我不知道要搜索什么...
def foo(q):
l = sorted(q)
ln = range(len(l))
for x in ln:
if len(l[x:]) > 1:
for y in ln[x + 1:]:
if (len(l[y:]) > 0) and (l[y] % l[x] == 0):
for z in ln[y + 1:]:
if l[z] % l[y] == 0:
ans += 1
return ans
这个有点快:
def bar(q):
l = sorted(q)
ans = 0
for x2, x in enumerate(l):
pool = l[x2 + 1:]
if len(pool) > 1:
for y2, y in enumerate(pool):
pool2 = pool[y2 + 1:]
if pool2 and (y % x == 0):
for z in pool2:
if z % y == 0:
ans += 1
return ans
这是我在大家的帮助下想出的,但我一定做错了什么,因为它得到了错误的答案(虽然它真的很快):
def function4(numbers):
ans = 0
num_dict = {}
index = 0
for x in numbers:
index += 1
num_dict[x] = [y for y in numbers[index:] if y % x == 0]
for x in numbers:
for y in num_dict[x]:
for z in num_dict[y]:
print(x, y, z)
ans += 1
return ans
(39889
代替40888
) - 哦,我不小心让索引 var 从 1 而不是 0 开始。现在可以了。
最终编辑
通过重新评估我需要它做什么,我找到了找到三元组数量的最佳方法。该方法实际上并没有找到三元组,它只是对它们进行计数。
def foo(l):
llen = len(l)
total = 0
cache = {}
for i in range(llen):
cache[i] = 0
for x in range(llen):
for y in range(x + 1, llen):
if l[y] % l[x] == 0:
cache[y] += 1
total += cache[x]
return total
这是该函数的一个版本,它解释了思考过程(尽管由于垃圾邮件打印,但不适合庞大的列表):
def bar(l):
list_length = len(l)
total_triples = 0
cache = {}
for i in range(list_length):
cache[i] = 0
for x in range(list_length):
print("\n\nfor index[{}]: {}".format(x, l[x]))
for y in range(x + 1, list_length):
print("\n\ttry index[{}]: {}".format(y, l[y]))
if l[y] % l[x] == 0:
print("\n\t\t{} can be evenly diveded by {}".format(l[y], l[x]))
cache[y] += 1
total_triples += cache[x]
print("\t\tcache[{0}] is now {1}".format(y, cache[y]))
print("\t\tcount is now {}".format(total_triples))
print("\t\t(+{} from cache[{}])".format(cache[x], x))
else:
print("\n\t\tfalse")
print("\ntotal number of triples:", total_triples)