时间戳

首页 > 解决方案 > 检查列表中是否已经存在元素之间的差异

python - 检查列表中是否已经存在元素之间的差异

问题描述

我正在尝试为最简单的可行Golomb Ruler建立一个启发式方法。从 0 到 n，找到 n 个数，使得它们之间的所有差异都不同。这种启发式方法包括每次将标尺增加 1。如果列表中已经存在差异，则跳转到下一个整数。所以标尺以 [0,1] 开头，差异列表 = [ 1 ]。然后我们尝试将 2 加到标尺 [0,1,2] 上，但这不可行，因为差异 (2-1 = 1) 已经存在于差异列表中。然后我们尝试将 3 加到标尺 [0,1,3] 上，这是可行的，因此差异列表变为 [1,2,3] 等等。到目前为止，这是我所做的：

n = 5
positions = list(range(1,n+1))
Pos = []
Dist = []
difs = []
i = 0


while (i < len(positions)):
    if len(Pos)==0:
        Pos.append(0)
        Dist.append(0)
    elif len(Pos)==1:
            Pos.append(1)
            Dist.append(1)
    else:
        postest = Pos + [i] #check feasibility to enter the ruler
        difs = [a-b for a in postest for b in postest if a > b] 
        if any (d in difs for d in Dist)==True:
                pass
        else:
            for d in difs:
                Dist.append(d) 
            Pos.append(i) 
    i += 1

但是，我无法使差异检查起作用。有什么建议么？

标签： pythonpython-3.xheuristics

解决方案

为了提高效率，我倾向于使用集合来存储差异，因为它们有利于包含测试，并且您不关心排序（可能直到您实际打印出来，此时您可以使用sorted）。

您可以使用临时集来存储您正在测试的数字与您当前拥有的数字之间的差异，然后将其添加到现有集，或者如果找到任何匹配项则将其丢弃。（注意循环else块for，如果break没有遇到就会执行。）

n = 5

i = 0
vals = []
diffs = set()
while len(vals) < n:
    diffs1 = set()
    for j in reversed(vals):
        diff = i - j
        if diff in diffs:
            break
        diffs1.add(diff)
    else:
        vals.append(i)
        diffs.update(diffs1)
    i += 1

print(vals, sorted(diffs))

显式循环值（而不是使用）是为了避免不必要地计算候选数与所有any现有值之间的差异，当大多数候选数不成功并且循环可以在找到第一个匹配项后提前中止。

它vals也可以作为一个集合并使用add而不是append（尽管类似地，您可能希望sorted在打印时使用它）。在这种情况下，使用了一个列表，尽管原则上迭代它的顺序并不重要，但此代码会以相反的顺序迭代以首先测试较小的差异，因为可能会更快地拒绝不可用的候选者方式。使用 n=200 进行测试，代码运行了大约 0.2 秒，reversed没有运行大约 2.1秒reversed；随着增加，效果逐渐变得更加明显n。在 n=400 的情况下，无论有无reversed.

推荐阅读