时间戳

首页 > 解决方案 > 如何按“国际象棋顺序”对数组或查询集进行排序？

python - 如何按“国际象棋顺序”对数组或查询集进行排序？

问题描述

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

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)等方式进行排序。

标签： pythondjangosorting

解决方案

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

具有最小元素 x min和最大元素 x max的列表l如果是 x min则按照国际象棋排序顺序，并递归地选择以最小化步长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]

适用于您的问题

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

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

推荐阅读