Sắp xếp danh sách: các số tăng dần, các chữ cái trong giảm dần

Question

Câu hỏi này thực sự được điều chỉnh từ one previously asked by Mat.S (image). Mặc dù nó đã bị xóa, tôi nghĩ rằng đó là một câu hỏi hay, vì vậy tôi đang reposting nó với các yêu cầu rõ ràng hơn và giải pháp của riêng tôi.

---

Cho một danh sách các chữ cái và con số, nói

['a', 2, 'b', 1, 'c', 3] 

Yêu cầu là để sắp xếp các số tăng dần và chữ cái trong giảm dần, mà không thay đổi vị trí tương đối của các chữ cái và số. Bằng cách này, tôi có nghĩa là nếu danh sách không được phân loại là:

[L, D, L, L, D] # L -> letter; # D -> digit 

Sau đó, danh sách được sắp xếp cũng phải

[L, D, L, L, D] 

1. Các chữ cái và chữ số làm không nhất thiết thay thế trong một mô hình thường xuyên - chúng có thể xuất hiện theo bất kỳ thứ tự tùy ý nào

2. Sau khi sắp xếp - số tăng dần, các chữ cái sẽ giảm dần.

Vì vậy, cho ví dụ trên đầu ra là

['c', 1, 'b', 2, 'a', 3] 

Một ví dụ khác:

In[]: [5, 'a', 'x', 3, 6, 'b'] 
Out[]: [3, 'x', 'b', 5, 6, 'a'] 

Điều gì sẽ là một cách tốt để làm điều này?

Answer 1

Dưới đây là một cách tiếp cận tối ưu hóa sử dụng defaultdict() và bisect():

In [14]: lst = [5, 'a', 'x', 3, 6, 'b'] 
In [15]: from collections import defaultdict  
In [16]: import bisect 

In [17]: def use_dict_with_bisect(lst): 
      d = defaultdict(list) 
      for i in lst: 
       bisect.insort(d[type(i)], i) 
      # since bisect doesn't accept key we need to reverse the sorted integers 
      d[int].sort(reverse=True) 
      return [d[type(i)].pop() for i in lst] 
    .....: 

Bản trình diễn:

In [18]: lst 
Out[18]: [5, 'a', 'x', 3, 6, 'b'] 

In [19]: use_dict_with_bisect(lst) 
Out[19]: [3, 'x', 'b', 5, 6, 'a'] 

Trong trường hợp bạn đang làm việc với các danh sách lớn hơn nó nhiều hơn tối ưu hóa để giảm sử dụng bisect trong đó có một độ phức tạp về O (n) và chỉ sử dụng python built-in sort() chức năng với nlog (n) phức tạp.

In [26]: def use_dict(lst): 
      d = defaultdict(list) 
      for i in lst: 
       d[type(i)].append(i) 
      d[int].sort(reverse=True); d[str].sort() 
      return [d[type(i)].pop() for i in lst] 

Benchmark với câu trả lời khác cho thấy cách tiếp cận mới nhất sử dụng dict và built-in sort gần như 1ms nhanh so với cách tiếp cận khác:

In [29]: def use_sorted1(lst): 
       letters = sorted(let for let in lst if isinstance(let,str)) 
       numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) 
       return [letters.pop() if isinstance(elt,str) else numbers.pop() for elt in lst] 
    .....: 

In [31]: def use_sorted2(lst): 
       f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) 
       f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) 
       return [next(f1) if isinstance(x, str) else next(f2) for x in lst] 
    .....: 

In [32]: %timeit use_sorted1(lst * 1000) 
100 loops, best of 3: 3.05 ms per loop 

In [33]: %timeit use_sorted2(lst * 1000) 
100 loops, best of 3: 3.63 ms per loop 

In [34]: %timeit use_dict(lst * 1000) # <-- WINNER 
100 loops, best of 3: 2.15 ms per loop 

Dưới đây là một chuẩn mực cho thấy cách sử dụng bisect có thể làm chậm quá trình cho danh sách dài:

In [37]: %timeit use_dict_with_bisect(lst * 1000) 
100 loops, best of 3: 4.46 ms per loop 

Answer 2

Look ma, không iter:

lst = ['a', 2, 'b', 1, 'c', 3] 
letters = sorted(let for let in lst if isinstance(let,str)) 
numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) 
lst = [(letters if isinstance(elt,str) else numbers).pop()for elt in lst] 

Tôi đang tìm kiếm một cách để tắt chức năng này thành một (khủng khiếp) one-liner, nhưng không may mắn cho đến nay - lời đề nghị chào đón!

Answer 3

tôi lấy một vết nứt ở này bằng cách tạo ra hai máy phát điện và sau đó lấy từ họ có điều kiện:

In [116]: f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) 

In [117]: f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) 

In [118]: [next(f1) if isinstance(x, str) else next(f2) for x in lst] 
Out[118]: ['c', 1, 'b', 2, 'a', 3] 

Answer 4

Trong một dòng:

list(map(list, sorted(zip(lst[::2], lst[1::2]), key=lambda x: x[1] if hasattr(x[0], '__iter__') else x[0]))) 

Answer 5

To kiểm đếm không được khuyến khích, nhưng tôi đã vui vẻ mã hóa nó.

from collections import deque 
from operator import itemgetter 

lst = ['a', 2, 'b', 1, 'c', 3] 
is_str = [isinstance(e, str) for e in lst] 
two_heads = deque(map(itemgetter(1), sorted(zip(is_str, lst)))) 
[two_heads.pop() if a_str else two_heads.popleft() for a_str in is_str] 

Answer 6

Sao chúng ta không chỉ sắp xếp danh sách theo thứ tự tăng dần, nhưng đảm bảo rằng số đến trước chữ:

[D, D, L, L, L] # L -> letter; # D -> digit 

Chúng ta có thể đạt được điều đó theo cách như vậy:

>>> lst = [5, 'a', 'x', 3, 6, 'b'] 
>>> sorted(lst, key=lambda el: (isinstance(el, str), el)) 
[3, 5, 6, 'a', 'b', 'x'] 

Sau đó, chúng ta nhìn qua mảng ban đầu từ trái sang phải và nếu chúng ta gặp phải số, chúng ta chọn phần tử từ đầu mảng đã sắp xếp, nếu không thì từ đầu. Các giải pháp tiết đầy đủ sau đó sẽ là:

def one_sort(lst): 
    s = sorted(lst, key=lambda el: (isinstance(el, str), el)) 
    res = [] 
    i, j = 0, len(s) 
    for el in lst: 
     if isinstance(el, str): 
      j -= 1 
      res.append(s[j]) 
     else: 
      res.append(s[i]) 
      i += 1 
    return res 

lst = [5, 'a', 'x', 3, 6, 'b'] 
print(one_sort(lst)) # [3, 'x', 'b', 5, 6, 'a'] 

Hầu ngắn nhưng giải pháp khó hiểu sẽ là:

def one_sort_cryptic(lst): 
    s = sorted(lst, key=lambda el: (isinstance(el, str), el)) 
    return [s.pop(-isinstance(el, str)) for el in lst] 

lst = [5, 'a', 'x', 3, 6, 'b'] 
print(one_sort_cryptic(lst)) # [3, 'x', 'b', 5, 6, 'a']