按属性值对对象进行排序而不允许间隙或重复的算法

Question

我有一个包含多个日期的议程，每个日期可以包含 0 > ... 个项目。项目可以按位置排序，位置应为无间隙和重复的整数值。

class Item(models.Model):
    date = models.DateField()
    position = models.IntegerField()

    def move_to(position):
        qs = self.__class__.objects.filter(date=self.date)

        # if the position is taken, move up all items gte position
        # 1 spot to free the wanted position

        if position in qs.values_list('position', flat=True):
            qs.filter(position__gte=position).update(position=F('position') + 1)
        self.position = position
        self.save()

这有点管用，但如果我在日期之间来回移动项目，我就会留下位置差距，例如

"1, 4, 13"

所以它不会截断差距，我试图寻找算法，但 MPTT 和类似的东西似乎有点矫枉过正我对父层次结构没有任何要求

更新

我想出了一个算法，似乎可以满足我的要求，但我不确定如何实现它

l = [0, 2, 13]

def is_compressed(l):
    return len(l) == sum(l)

while not is_compressed(l):
    m = 0
    for i in l[m:]:
        while i - 1 >= 0 and i - 1 not in l:
            m += 1
            index = l.index(i)
            l.remove(i)
            l.insert(index, i - 1)

>>> print l
[0, 1, 2]

Answer 1

上述算法将不起作用，因为假设您有以下列表 -

[0,2,5,9]

理想情况下你应该得到 -

[0,1,2,3]

那个列表的总和是 6 ，但是列表的长度是 4 ，这不符合你在 is_compressed() 中的条件。

算法应该类似于 -

l = [0, 2, 13, 15]

next_i = 0
for k,j in enumerate(l):
    if j != next_i:
        l[k] = next_i
    next_i = next_i + 1

print(l)
>> [0, 1, 2, 3]

要在您的程序中实现，您可以对位置进行类似的测试，并在对象内的位置不是下一个预期位置时更改该位置。

按属性值对对象进行排序而不允许间隙或重复的算法

Algorithm to sort object by attribute value without allowing gaps or duplicates

python

sql

sorting

django

django-orm