Check if differences between elements already exists in a list

user_9346167 0
Viewed 97

I'm trying to build a heuristic for the simplest feasible Golomb Ruler as possible. From 0 to n, find n numbers such that all the differences between them are different. This heuristic consists of incrementing the ruler by 1 every time. If a difference already exists on a list, jump to the next integer. So the ruler starts with [0,1] and the list of differences = [ 1 ]. Then we try to add 2 to the ruler [0,1,2], but it's not feasible, since the difference (2-1 = 1) already exists in the list of differences. Then we try to add 3 to the ruler [0,1,3] and it is feasible, and thus the list of differences becomes [1,2,3] and so on. Here's what I've come to so far:

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

However I can't make the differences check to work. Any suggestions?

heuristics python-3.x python
1 Answers

For efficiency I would tend to use a set to store the differences, because they are good for inclusion testing, and you don't care about the ordering (possibly until you actually print them out, at which point you can use sorted).

You can use a temporary set to store the differences between the number that you are testing and the numbers you currently have, and then either add it to the existing set, or else discard it if you find any matches. (Note else block on for loop, that will execute if break was not encountered.)

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))

The explicit loop over values (rather than the use of any) is to avoid unnecessarily calculating the differences between the candidate number and all the existing values, when most candidate numbers are not successful and the loop can be aborted early after finding the first match.

It would work for vals also to be a set and use add instead of append (although similarly, you would probably want to use sorted when printing it). In this case a list is used, and although it does not matter in principle in which order you iterate over it, this code is iterating in reverse order to test the smaller differences first, because the likelihood is that unusable candidates are rejected more quickly this way. Testing it with n=200, the code ran in about 0.2 seconds with reversed and about 2.1 without reversed; the effect is progressively more noticeable as n increases. With n=400, it took 1.7 versus 27 seconds with and without the reversed.

user_135960370
Related