带相邻差异的python排序

Question

我有一份物品清单

item = [a,a,a,b,b,b,b,c,c,c,c,c,e,e,e,e,e,e]

我想用混合顺序排序，所以相邻允许最大重复两次，例如

[a,a,b,a,b,b,c,c,b,b,c,e,c,c,e,e,e,e,e]

因为没有更多的项目可以与e洗牌，所以e将保持与相邻的重复。

有什么快速的方法来解决这个问题吗？

编辑

为了说明清楚，给它一个真实的例子，在一个笔记本电脑类别中，我有100种来自IBM的产品，10种来自宏碁的产品，6种来自苹果的产品，我想对相同的品牌进行排序，使它们尽可能的混合。

例如，我有未排序的列表

[{brand:"ibm", "id":1},{brand:"ibm", "id":2},{brand:"ibm", "id":3},{brand:"ibm", "id":4},{brand:"ibm", "id":5},{brand:"ibm", "id":6},{brand:"acer", "id":7},{brand:"acer", "id":8},{brand:"acer", "id":9},{brand:"acer", "id":10},{brand:"apple", "id":11},{brand:"apple", "id":12}]

目标结果，只要同一个品牌不相邻，就像前10名都来自同一个品牌，但可以2-3个品牌相邻，

[{brand:"ibm", "id":1},,{brand:"acer", "id":7},{brand:"ibm", "id":2},{brand:"ibm", "id":3},{brand:"acer", "id":8},{brand:"apple", "id":12}{brand:"ibm", "id":4},{brand:"acer", "id":9},{brand:"ibm", "id":5},{brand:"ibm", "id":6},{brand:"acer", "id":10}]

这将是很好的不使用随机，但使用确定性排序，所以每次用户仍然看到相同的顺序，但这不是必须的，因为它可以保存到缓存。

谢谢

Answer 1

第二次编辑

好吧，现在我明白了。你的声音听起来就像洗牌，其实不是那样的。这是一个答案，更多地涉及到。

首先，我想介绍一下pprint。这只是print的一个版本，它很好地格式化了事物：

from pprint import pprint
pprint(items)
#>>> [{'brand': 'ibm', 'id': 1},
#>>>  {'brand': 'ibm', 'id': 2},
#>>>  {'brand': 'ibm', 'id': 3},
#>>>  {'brand': 'ibm', 'id': 4},
#>>>  {'brand': 'ibm', 'id': 5},
#>>>  {'brand': 'ibm', 'id': 6},
#>>>  {'brand': 'acer', 'id': 7},
#>>>  {'brand': 'acer', 'id': 8},
#>>>  {'brand': 'acer', 'id': 9},
#>>>  {'brand': 'acer', 'id': 10},
#>>>  {'brand': 'apple', 'id': 11},
#>>>  {'brand': 'apple', 'id': 12}]

别挡道，我们走吧。

我们要按品牌分组：

from collections import defaultdict

brand2items = defaultdict(list)

for item in items:
    brand2items[item["brand"]].append(item)

pprint(brand2items)
#>>> {'acer': [{'brand': 'acer', 'id': 7},
#>>>           {'brand': 'acer', 'id': 8},
#>>>           {'brand': 'acer', 'id': 9},
#>>>           {'brand': 'acer', 'id': 10}],
#>>>  'apple': [{'brand': 'apple', 'id': 11}, {'brand': 'apple', 'id': 12}],
#>>>  'ibm': [{'brand': 'ibm', 'id': 1},
#>>>          {'brand': 'ibm', 'id': 2},
#>>>          {'brand': 'ibm', 'id': 3},
#>>>          {'brand': 'ibm', 'id': 4},
#>>>          {'brand': 'ibm', 'id': 5},
#>>>          {'brand': 'ibm', 'id': 6}]}

然后我们可以得到值，因为我们不在乎关键：

items_by_brand = list(brand2items.values())

pprint(items_by_brand)
#>>> [[{'brand': 'apple', 'id': 11}, {'brand': 'apple', 'id': 12}],
#>>>  [{'brand': 'ibm', 'id': 1},
#>>>   {'brand': 'ibm', 'id': 2},
#>>>   {'brand': 'ibm', 'id': 3},
#>>>   {'brand': 'ibm', 'id': 4},
#>>>   {'brand': 'ibm', 'id': 5},
#>>>   {'brand': 'ibm', 'id': 6}],
#>>>  [{'brand': 'acer', 'id': 7},
#>>>   {'brand': 'acer', 'id': 8},
#>>>   {'brand': 'acer', 'id': 9},
#>>>   {'brand': 'acer', 'id': 10}]]

现在我们要把结果交织在一起。基本的想法是，我们想要从最大的水池更经常地采取，因为它将花费时间最长的排气。所以每一次迭代我们都要花费最长的时间，而pop则是其中的一项，只是我们不想重复。我们可以采取两个不同的小组，两个最大的，并交错他们的结果。

当小组中没有剩下任何物品时，我们就停止。

from heapq import nlargest

shufflatored = []
while any(items_by_brand):
    items1, items2 = nlargest(2, items_by_brand, key=len)

    if items1: shufflatored.append(items1.pop())
    if items2: shufflatored.append(items2.pop())

heapq模块是一个鲜为人知但非常出色的模块。事实上，只要付出一定的努力，就可以通过将items_by_brand保持为一个堆来提高效率。但是，这并不是真正值得付出的努力，因为其他处理堆的工具不需要key，这需要一些模糊的解决方案。

就是这样。如果您希望允许加倍，则可以替换

    if items1: shufflatored.append(items1.pop())
    if items2: shufflatored.append(items2.pop())

使用

    if items1: shufflatored.append(items1.pop())
    if items1: shufflatored.append(items1.pop())
    if items2: shufflatored.append(items2.pop())
    if items2: shufflatored.append(items2.pop())

好了！

编辑

你想要确定性的东西吗？那你为什么不这么说？

lst = list(range(20))

lst[::2], lst[1::2] = lst[1::2], lst[::2]

lst
#>>> [1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18]

魔法，不是吗？

希望您了解此方法以就地交换值：

a = 1
b = 2

a, b = b, a

a
#>>> 2

b
#>>> 1

嗯，lst[::2]是所有其他的值

lst[::2]
#>>> [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

lst[1::2]是其他所有的值，

lst[1::2]
#>>> [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

因此，lst[::2], lst[1::2] = lst[1::2], lst[::2]将所有其他值与其他值交换！

import random

items = [1,1,1,2,2,2,2,3,3,3,3,3,4,4,4,4,4,4]

[
    iv[1] for iv in
    sorted(
        enumerate(items),
        key=lambda iv: iv[0]+random.choice([-1, 1])
    )
]

#>>> [1, 1, 2, 1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4]

[
    iv[1] for iv in
    sorted(
        enumerate(range(20)),
        key=lambda iv: iv[0]+random.choice([-1, 1])
    )
]
#>>> [0, 2, 1, 4, 3, 5, 6, 7, 9, 8, 11, 10, 12, 14, 13, 15, 17, 16, 18, 19]

这是一个随机的洗牌，所以第一个列表没有显示大多数洗牌。选择的结果是由各种可能性手工挑选的。

基本上，该算法获取一个列表并对其进行索引：

  items a b c d e f g h i j
indexes 0 1 2 3 4 5 6 7 8 9

然后根据索引+ [-1, 1]中的随机选择进行排序。

  items a b c d e f g h i j
indexes 0 1 2 3 4 5 6 7 8 9
sort by 1 0 3 2 5 4 5 6 9 8

和结果

  items b a d c f e g h j i
indexes 1 0 3 2 5 4 6 7 9 8
sort by 0 1 2 3 4 5 5 6 8 9

它被洗牌了。要改变洗牌的类型，例如，为了使它或多或少地洗牌，请更改列表[-1, 1]的具体内容。您还可以尝试[-1, 0, 1]、[0, 1]和其他变体。

该算法分步骤：

indexed = enumerate(items)

shuffled = sorted(indexed, key=lambda iv: iv[0]+random.choice([-1, 1]))

# Remove the index, extract the values out again
result = [iv[1] for iv in shuffled]

现在，效率。

如果您非常精明，您可能会意识到排序传统上是O(n log n)。Python使用了TimSort，这是一种很好的排序算法。尽管任何比较排序(又名。比较值的排序)必须至少有一个O(n log n)的上限，它们也可以有一个与O(n)一样低的下限！

这是因为，排序一个已经排序的列表是微不足道的，只要您检查它是否已排序。TimSort有一个本地化的“排序”概念，当值被排序时，它将很快检测到。这意味着，因为他们只是在某种程度上-洗牌TimSort将执行一些更接近O(kn)，其中k是“洗牌-的名单，这是远远低于log n！”