如何在"国际象棋顺序"中对数组或查询集进行排序？

Question

任务是按"国际象棋顺序"对查询集进行排序.即:

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)等的方式排序.

Answer 1

我从未听说过国际象棋排序,但从你的描述来看,它似乎是这样定义的.

如果是x _min,则具有最小元素x _min和最大元素x _max的列表l以国际象棋排序顺序并且被递归地拾取以最小化步骤k,步骤k被定义为最小正整数,使得mod x _max.l[0]l[j]l[j-1] + k == l[j]

换句话说,就像你只允许在棋盘上放置与其值相对应的列.如果每个元素在棋盘上尽可能早地定位,则该列表被认为是有序的.

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

虽然,我们可以编写一个类似于按国际象棋顺序排序的计数排序的算法.

码

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)