CODEWITHSUNDEEP
pythonpython-3.xsorting
GusN
GusN

Reputation: 63

Sort a list by a key and sort another list in the same way as the first?

For example there are three lists:

unsorted_key = ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p']
sorted_key = ['e', 'i', 'o', 'p', 'q', 'r', 't', 'u', 'w', 'y']
ciphertext = [
              ['u', 't', 'x', 'e'],
              ['p', 'r', 'k', 'p'],
              ['v', 'n', 'x', 'a'],
              ['n', 'h', 'e', 'x'],
              ['x', 'h', 'm', 's'],
              ['l', 'x', 'c', 'x'],
              ['x', 'c', 'y', 'a'],
              ['t', 'u', 'o', 'x'],
              ['e', 'r', 'm', 'e'],
              ['y', 'y', 'e', 'x']
             ]

Is it possible to take the order of the sorted_key and sort it into the unsorted_key, and take the order of the ciphertext and sort it in an identical way?

When moving 'q' from sorted_key[4] to sorted_key[0], it should move ciphertext[4] to ciphertext[0].

I've been thinking about it and the only way I can think of would be to use a helper function to dynamically generate and return a lambda function from the order of unsorted_key, and then use something like:

sorted_key, ciphertext = (list(i) for i in zip(*sorted(zip(sorted_key, ciphertext), key=generate(unsorted_key))))

But I really don't know how zip() or lambda functions work or how to make a custom sorting order into one, or if one can even be returned to be used in sorted(). I really can't seem to wrap my head around this problem, so any help would be greatly appreciated!

Upvotes: 2

Views: 652

Answers (4)

iGian
iGian

Reputation: 11193

I'm not sure I get the point, but...

First determine the moves (can be the opposite, it0s not clear to me):

moves = [ [i, sorted_key.index(c)] for i, c in enumerate(unsorted_key) ]
#=> [[0, 4], [1, 8], [2, 0], [3, 5], [4, 6], [5, 9], [6, 7], [7, 1], [8, 2], [9, 3]]

Maybe swap elements in [i, sorted_key.index(c)].

Apply the moves to a receiver (res):

res = [ None for _ in range(len(ciphertext))]
for a, b in moves:
  res[a] = ciphertext[b]

So the output should be:

for line in res:
  print(line)

# ['x', 'h', 'm', 's']
# ['e', 'r', 'm', 'e']
# ['u', 't', 'x', 'e']
# ['l', 'x', 'c', 'x']
# ['x', 'c', 'y', 'a']
# ['y', 'y', 'e', 'x']
# ['t', 'u', 'o', 'x']
# ['p', 'r', 'k', 'p']
# ['v', 'n', 'x', 'a']
# ['n', 'h', 'e', 'x']

For testing execution time

import timeit, functools

def custom_sort(ciphertext, sorted_key, unsorted_key):
  return [ ciphertext[b] for _, b in [ [i, sorted_key.index(c)] for i, c in enumerate(unsorted_key) ] ]


custom_sort = timeit.Timer(functools.partial(custom_sort, ciphertext, sorted_key, unsorted_key))

print(custom_sort.timeit(20000))

Upvotes: 1

blhsing
blhsing

Reputation: 106946

An efficient approach to solve this problem in linear time is to create a dict that maps keys to indices of sorted_key, and then create a mappping dict that maps indices of unsorted_key to indices of sorted_key based on the same keys, so that you can iterate an index through the range of length of ciphertext to generate a list in the mapped order:

order = dict(map(reversed, enumerate(sorted_key)))
mapping = {i: order[k] for i, k in enumerate(unsorted_key)}
print([ciphertext[mapping[i]] for i in range(len(ciphertext))])

This outputs:

[['x', 'h', 'm', 's'], ['e', 'r', 'm', 'e'], ['u', 't', 'x', 'e'], ['l', 'x', 'c', 'x'], ['x', 'c', 'y', 'a'], ['y', 'y', 'e', 'x'], ['t', 'u', 'o', 'x'], ['p', 'r', 'k', 'p'], ['v', 'n', 'x', 'a'], ['n', 'h', 'e', 'x']]

Upvotes: 1

r.ook
r.ook

Reputation: 13888

The builtin sorted with a custom key can do it for you:

sorted(ciphertext, key=lambda x: unsorted_key.index(sorted_key[ciphertext.index(x)]))

Output:

[['x', 'h', 'm', 's'], 
 ['e', 'r', 'm', 'e'], 
 ['u', 't', 'x', 'e'], 
 ['l', 'x', 'c', 'x'], 
 ['x', 'c', 'y', 'a'], 
 ['y', 'y', 'e', 'x'], 
 ['t', 'u', 'o', 'x'], 
 ['p', 'r', 'k', 'p'], 
 ['v', 'n', 'x', 'a'], 
 ['n', 'h', 'e', 'x']]

The lambda basically boils down to:

  1. Find the current index
  2. Find the value of current index in sorted_key
  3. Find the index of sorted_key value in unsorted_key
  4. Sort it

The one thing that I'm not clear about is why do you need to "sort" sorted_key if the end result is identical to unsorted_key? Just sorted_key = unsorted_key[:] is simple enough if that's the case. But if you really need to sort sorted_key as well, you can do this (it would actually make the lambda simpler):

ciphertext, sorted_key = map(list, zip(*sorted(zip(ciphertext, sorted_key), key=lambda x: unsorted_key.index(x[1]))))

ciphertext
[['x', 'h', 'm', 's'], 
 ['e', 'r', 'm', 'e'], 
 ['u', 't', 'x', 'e'], 
 ['l', 'x', 'c', 'x'], 
 ['x', 'c', 'y', 'a'], 
 ['y', 'y', 'e', 'x'], 
 ['t', 'u', 'o', 'x'], 
 ['p', 'r', 'k', 'p'], 
 ['v', 'n', 'x', 'a'], 
 ['n', 'h', 'e', 'x']]

sorted_key
['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p']

Upvotes: 1

J. Taylor
J. Taylor

Reputation: 4865

I'm not sure I'm understanding your question properly, but if you're attempting to sort the unsorted key, and ensure that the ciphertexts are sorted accordingly, this should do what you want:

pairs = zip(unsorted_key, ciphertext)
sorted_key = []
sorted_ciphertexts = []
for t in sorted(pairs):
   sorted_key.append(t[0])
   sorted_ciphertexts.append(t[1])

I'm sure there's probably a more elegant way to do it, but this will ensure that the key and ciphertexts are placed at the same index.

Upvotes: 0

Related Questions