时间戳

首页 > 解决方案 > 如何有效地处理大的排列迭代？

python - 如何有效地处理大的排列迭代？

问题描述

如何有效地解决这样的
问题问题
具有目标值 K range(10^6) 的范围数组 (1<s<e<10^9) 需要找到总和为偶数的对

form itertools import product
counter=0
for i in product(array,repeat=k):
    if sum(i)%2==0
        counter+=1
print(counter)

由于上述代码的问题是它总是在TLE中运行很长的数字，有什么建议可以有效地解决这类问题吗？样本输入
范围（1,10）k=2 arr=[1,2,3,4,5,6,7,8,9,10]
样本输出 {1,1},{1,3},{1,9}.......{10,8},{10,10}在范围（1,10）中总共有 50 对这样的对

标签： pythonalgorithmoptimizationdata-structurespermutation

解决方案

我会这样解决它：
假设有很多重复项，我将索引列表中的所有不同元素，而不是多次传递列表中的每个项目。例如，整数 1 到 15 的随机分布，重复 100 次。然后提供该列表，我会将它们放在字典中并比较索引：

如果键重复超过 2 次，如果它是奇数或偶数，则总和为偶数。
否则，如果该键与另一个键的总和为偶数，则检索这两个键的所有索引。

import secrets
from collections import defaultdict

x=0
randomlist = []
while x<100:
    y=secrets.choice(range(1,15))
    randomlist.append(y)
    x=x+1

ddict = defaultdict(list)
for i,r in enumerate(randomlist):
    ddict[r].append(i)
print(ddict)
for k,v in ddict.items():
    if len(v)>=2:
        print("even sum - " + str(k) + " : " + str(v))
    for i,j in ddict.items():
        if (k+i)%2==0 and k!=i:
            print("even sum - " + str(k) + " : " + str (i)+ " : " + str(v) + str(j))

推荐阅读