python之如何对 "chess order"中的数组或查询集进行排序

任务是按照“国际象棋顺序”对查询集进行排序。即:

class Item(models.Model): 
    CHOICES = [ 
        (1, 1), 
        (2, 2), 
        (3, 3), 
    ] 
    branch = models.PositiveSmallIntegerField(choices=CHOICES) 
 
item1.branch == 1 
item2.branch == 1 
item3.branch == 2 
item4.branch == 3 
item5.branch == 3 

Item.objects.all() 的期望输出会是:

[item1, item3, item4, item2, item5] 

因此，结果查询集将以分支为 (1,2,3), (1,2,3), (1,2,3) 的方式排序等

请您参考如下方法:

我从来没有听说过国际象棋排序，但从你的描述来看它似乎是这样定义的。

A list l with smallest element x_min and greatest element x_max is in chess sort order if l[0] is x_min and l[j] is recursively picked to minimize the step k which is defined as the smallest positive integer such that l[j-1] + k == l[j] mod x_max.

换句话说，这就像你只能将项目放在棋盘上对应于它们的值的列上。如果每个元素都尽可能早地在棋盘上定位，则认为该列表已排序。

这种排序的问题在于它不是本地的。这意味着相对于其邻居正确放置的每个项目并不意味着整个列表已正确排序。这很重要，因为它表明我们将无法使用 sorted 和精心设计的 key 参数对列表进行排序。

不过，我们可以编写一个类似于counting sort 的算法按国际象棋顺序排序。

代码

from collections import defaultdict, deque 
from itertools import cycle 
 
def chess_sort(lst, key=lambda x: x): 
    count = defaultdict(deque) 
    for x in lst: 
        count[key(x)].append(x) 
 
    order = sorted(count) 
    output = [] 
 
    for x in cycle(order): 
        if len(output) == len(lst): 
            break 
        if count[x]: 
            output.append(count[x].popleft()) 
 
    return output 

例子

import random 
 
lst = random.choices(range(5), k=15) 
 
print('list:', lst) 
print('sorted:', chess_sort(lst)) 

输出

list: [0, 1, 4, 2, 1, 2, 1, 3, 4, 3, 0, 0, 0, 3, 2] 
sorted: [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 0] 

应用于你的问题

请注意我是如何允许将 key 传递给 chess_sort 的？您可以像使用 sorted 一样使用它来按 branch 属性对项目进行排序。

chess_sort(Item.objects.all(), key=lambda x: x.branch)