python - Comparisons between an arbitrary number of lists of arbitrary length Python

Question

Given an arbitrary number of lists of integers of arbitrary length, I would like to group the integers into new lists based on a given distance threshold.

Input:

l1 = [1, 3]
l2 = [2, 4, 6, 10]
l3 = [12, 13, 15]
threshold = 2

Output:

   [1, 2, 3, 4, 6] # group 1
   [10, 12, 13, 15] # group 2

The elements of the groups act as a growing chain so first we have

abs(l1[0] - l2[0]) < threshold #true

so l1[0] and l2[0] are in group 1, and then the next check could be

abs(group[-1] - l1[1]) < threshold #true

so now l1[1] is added to group 1

Is there a clever way to do this without first grouping l1 and l2 and then grouping l3 with that output?

标签： pythonlistloopsgraph

Answer 1

Based on the way that you asked the question, it sounds like you just want a basic python solution for utility, so I'll give you a simple solution.

Instead of treating the lists as all separate entities, it's easiest to just utilize a big cluster of non-duplicate numbers. You can exploit the set property of only containing unique values to go ahead and cluster all of the lists together:

# Throws all contents of lists into a set, converts it back to list, and sorts
elems = sorted(list({*l1, *l2, *l3}))
# elems = [1, 2, 3, 4, 6, 10, 12, 13, 15]

If you had a list of lists that you wanted to perform this on:

lists = [l1, l2, l3]
elems = []
[elems.extend(l) for l in lists]
elems = sorted(list(set(elems)))
# elems = [1, 2, 3, 4, 6, 10, 12, 13, 15]

If you want to keep duplicated:

elems = sorted([*l1, *l2, *l3])
# and respectively
elems = sorted(elems)

From there, you can just do the separation iteratively. Specifically:

• Go through the elements one-by-one. If the next element is validly spaced, add it to the list you're building on.
• When an invalidly-spaced element is encountered, create a new list containing that element, and start appending to the new list instead.

This can be done as follows (note, -1'th index refers to last element):

out = [[elems[0]]]
thresh = 2
for el in elems[1:]:
    if el - out[-1][-1] <= thresh:
        out[-1].append(el)
    else:
        out.append([el])

# out = [[1, 2, 3, 4, 6], [10, 12, 13, 15]]