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

Question

我正在尝试构建一个尽可能最简单可行的启发式算法 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

但是我无法进行差异检查。有什么建议吗？

Answer 1

为了效率，我倾向于使用一组来存储差异，因为它们有利于包含测试，并且您不关心顺序（可能直到您实际打印出来，此时您可以使用 sorted).

您可以使用一个临时集合来存储您正在测试的数字与您当前拥有的数字之间的差异，然后将其添加到现有集合中，或者如果找到任何匹配项则将其丢弃。（注意 for 循环上的 else 块，如果没有遇到 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 测试它，使用 reversed 时代码运行大约需要 0.2 秒，没有 reversed 时大约需要 2.1 秒；随着 n 的增加，效果逐渐变得更加明显。当 n=400 时，使用和不使用 reversed.

需要 1.7 秒，而 27 秒

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

Check if differences between elements already exists in a list

python

heuristics

python-3.x