以自定义方式对数组进行排序的算法

Question

我正在寻找一种以自定义方式对数组进行排序的算法，但我没有成功找到解决问题的正确方法。我将使用类似 Django 的语法来描述代码，但没有必要仅限于 Django 的解决方案。

假设我有以下模型（类）：

class Website(models.Model):
    ...
class Offer(models.Model):
    website = models.ForeignKey(Website, on_delete=models.CASCADE)
    ...

假设我有以下实例：

• Offer 1 ->网站 A
• 报价 2 ->网站 B
• 报价 3 ->网站 B
• 报价 4 ->网站 B
• 报价 5 ->网站 C
• 优惠 6 ->网站 A
• 报价 7 ->网站 A
• 报价 8 ->网站 C

此实例形成一个序列（数组）：

sequence = [Offer 1, Offer 2, Offer 3, Offer 4, Offer 5, Offer 6, Offer 7, Offer 8]

我需要按照优惠的方式对序列进行排序同一网站不能依次排列，但原始订单应尽可能保持相同。

因此，排序顺序应如下所示：

sequence = [Offer 1, Offer 2, Offer 5, Offer 3, Offer 6, Offer 4, Offer 7, Offer 8]

正例：

• 网站 A、网站 B、网站 A、网站 C、网站 A
• 网站 A、网站 B、网站 C、网站 B、网站 C
• 网站 A、网站 B、网站 A、网站 B、网站 A

负面示例：

• 网站 A、网站 B、网站 B、网站 A、网站 B、...
• 网站 B、网站 C、网站 A、网站 A 、网站B、...
• 网站B、网站C、网站A、网站C、网站 C，...

感谢您的任何建议。

Answer 1

试试这个：

def sort_custom(offers):
    sorted_offers, sorted_count, index = [], len(offers), 0
    while sorted_count > 0:
        item = offers[index]
        if not sorted_offers or sorted_offers[-1] != item:
            sorted_offers.append(item)
            sorted_count -= 1
            del offers[index]
            if index > 0: index = 0
        else:
            if index < len(offers) - 1:
                index += 1
            else:
                sorted_offers += offers
                break
    return sorted_offers

用法：

>> lst = ['A', 'B', 'B', 'B', 'C', 'A', 'A', 'C']
>> sort_custom(lst)
['A', 'B', 'C', 'B', 'A', 'B', 'A', 'C']
>> lst2 = ['C', 'A', 'C', 'A', 'C', 'A', 'A', 'A']
>> sort_custom(lst2)
['C', 'A', 'C', 'A', 'C', 'A', 'A', 'A']

时间：

>> # for lst = ['A', 'B', 'B', 'B', 'C', 'A', 'A', 'C']
>> timer.repeat(3, 2000000)
[0.4880218505859375, 0.4770481586456299, 0.4776880741119385]

Answer 2

这应该可行：

def gen_best_order(orig):
    last = None
    while len(orig) > 0:
        deli = None
        for i, m in enumerate(orig):
            if m.website != last.website:
                last = m
                deli = i
                yield m
                break
        if deli is None:
            last = orig[0]
            yield orig[0]
            deli = 0
        del orig[deli]
ordered = list(gen_best_order(sequence))

这是一个生成器，它将尝试按顺序生成元素，但如果下一个元素等于生成的最后一个元素，它将跳过它。如果它到达列表的末尾并且没有办法产生不等于前一个的东西，它无论如何都会产生它。

这是一个处理数字列表的示例：

def gen_best_order(orig):
    last = None
    while len(orig) > 0:
        deli = None
        for i, m in enumerate(orig):
            if m != last:
                last = m
                deli = i
                yield m
                break
        if deli is None:
            last = orig[0]
            yield orig[0]
            deli = 0
        del orig[deli]

nums = [1,2,3,3,4,5,5]        
print 'orig:', nums
print 'reordered:', list(gen_best_order(nums))

这将打印：

orig: [1, 2, 3, 3, 4, 5, 5]
reordered: [1, 2, 3, 4, 3, 5, 5]