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将与邻居保持重复.

有没有快速的方法来排序这个？

编辑

为了说清楚,给它一个真实的例子,在笔记本电脑类别中,我有来自IBM的100个产品,来自Acer的10个产品,来自Apple的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堆积,可以通过相当多的努力使这更有效.然而,这并不值得努力,因为使用堆的其他工具不需要keys,这需要模糊的解决方法.

就是这样了.如果你想允许加倍,你可以更换

    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]

这是一个随机的随机播放,因此第一个列表不显示大多数shuffle.选择的结果是手工挑选的所有可能性.

基本上,该算法采用一个列表并对其进行索引:

  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

它被洗牌了.要更改shuffle的类型,比如说要使其更多或更少地随机播放,请更改列表的细节[-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!