Suppose I have two lists of numbers named v1 and v2. v2 has some of the same numbers as v1. It also has other numbers that are not in v1. I need to sort v2 such that all the numbers in the intersection of v1 and v2 end up in the same order; the order in v2 has to change minimally to match the order in v1 on just the shared elements. It should move the fewest items possible and not move items that are not in v1. Example:

v1 = [2, 3, 5, 7, 9]
v2 = [10, 7, 6, 5, 4]
after sort, v2 = [10, 5, 6, 7, 4] or [10, 6, 5, 7, 4]

Each of those results has 4 moves and I can't see a way to do it in fewer moves. At present I was thinking that I could build a set with all ordered pairs and use that in a comparator. When I have large data, though, this seems like a bad plan as I'll end with n^2 tuples in my set. Is there some better way?

The question is somewhat similar to this C# question: Sort a List based on a Pre-Sorted List . However, I'm unsure how to apply the techniques there in Python. I'm also unsure if the intersection in python preserves order (or how I would put that result back into the larger list).

CodePudding user response：

You can sort based on the index of values in v1 if it exists in v1 else you can sort based on the index of values in v2:

>>> sorted(v2, key=lambda x: v1.index(x) if x in v1 else v2.index(x))
[10, 6, 5, 7, 4]

For performance, a better solution would probably be to create a dictionary for v1 with value as key and index as value as dictionaries are hashed, then implement the sorting:

>>> v1_map={v:idx for idx,v in enumerate(v1)}
>>> list(map(lambda x: x[1], sorted(enumerate(v2), key=lambda x:v1_index if (v1_index:=v1_map.get(x[1])) else x[0])))
[10, 6, 5, 7, 4]

CodePudding user response：

oooo set theory... standby...