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

Question

我正在尝试建立一个最简单可行的启发式的 戈隆尺 尽可能的。从0到n，找到n个数，使它们之间的差值都不同。这个启发式包括每次将标尺递增1。如果列表上已经存在差值，则跳到下一个整数。所以尺子从[0,1]开始，差异列表=[ 1 ]。然后我们尝试在标尺[0,1,2]中添加2，但这是不可行的，因为差值（2-1=1）已经存在于差值列表中。然后我们尝试在标尺[0,1,3]上加上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).

您可以使用一个临时集来存储您正在测试的数字和您当前拥有的数字之间的差异，然后将其添加到现有的集中，否则，如果您发现任何匹配的数字，就将其丢弃。 (注意 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的情况下，使用和不使用的时间分别为1.7秒和27秒。reversed.