按屬性值排序對象而不允許空白或重複的算法

我有一個包含多個日期的日程，每個日期可以包含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之類的東西，似乎矯枉過正，我沒有對任何父層次結構requiement

更新

我想出了，似乎做我想做的算法，但我不知道如何實現它

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]

來源

2015-06-16 RabbitInAHole

請更新您收到的重複的問題。 –

看看[Queue.PriorityQueue]（https://docs.python.org/2/library/queue.html?highlight=priorityqueue#Queue.PriorityQueue） – smci

的AB奧雅納算法是行不通的，因爲假設你有下面的列表 -

[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]

要在你的程序執行，你可以做類似的測試與位置和改變物體，當不是下一個預期位置內的位置。

來源

2015-06-16 08:37:25

按屬性值排序對象而不允許空白或重複的算法

回答

相關問題