对物品进行排序，但防止相同名称的物品相邻；同时在集合中增加随机性。

问题描述 投票：-1回答：2

我想知道我需要用什么排序算法来创建一个 "最近 "的列表，但要防止名字相同的项目出现在彼此旁边，但也要能在集合中随机排序......。

例如，如果我们有以下的原始数据。

Apple   10/02/2020
Apple   15/02/2020
Apple   10/03/2020
Apple   15/03/2020
Apple   10/04/2020
Apple   15/04/2020
Banana  16/03/2020
Banana  21/03/2020
Banana  16/04/2020
Orange  13/03/2020
Orange  15/03/2020

我想把它排序，使它看起来像下图所示的数据（最近的项目从每个项目名称开始）。当然，我们没有橙子和香蕉了，所以最后4个项目都必须是苹果，但这也没办法。

Banana  16/04/2020
Apple   15/04/2020
Orange  15/03/2020
Banana  21/03/2020
Apple   10/04/2020
Orange  13/03/2020
Banana  16/03/2020
Apple   15/03/2020
Apple   10/03/2020
Apple   15/02/2020
Apple   10/02/2020

问题。重复的 "组"

这个排序顺序的唯一问题是，我们有一个重复的组，即 Banana, Apple, Orange 一遍又一遍。因此，我们想有选择地将一个组进行随机排序。"组 "的大小将由我们选择的一个数字来定义，而不是由项目的数量来定义。

因此，如果我们将 "组 "设置为3，它就会查看上面的顺序，并将每组的3个项目随机化，因此看起来像这样。

Orange  15/03/2020
Apple   15/04/2020
Banana  16/04/2020
---
Banana  21/03/2020
Orange  13/03/2020
Apple   10/04/2020
---
Banana  16/03/2020
Apple   15/03/2020
Apple   10/03/2020
---
Apple   10/02/2020
Apple   15/02/2020

问题： 失去了 "最近的"。

排序组的问题 以上 是指最近的项目被随机放在第一组的底部；当然这并不总是这样，但在这个例子中是这样的。

也许有一种方法可以保留第一组的顺序，并随机排列下面的组，或者只是重新排列，使组的顺序与之前的组的顺序不一样，例如：。

Banana  16/04/2020
Apple   15/04/2020
Orange  15/03/2020
---
Apple   10/04/2020
Orange  13/03/2020
Banana  21/03/2020
---
Banana  16/03/2020
Apple   15/03/2020
Apple   10/03/2020
---
Apple   15/02/2020
Apple   10/02/2020

例如：

Banana  16/04/2020
Apple   15/04/2020
Orange  15/03/2020
---
Banana  21/03/2020
Orange  13/03/2020
Apple   10/04/2020
---
Apple   15/03/2020
Banana  16/03/2020
Apple   10/03/2020
---
Apple   10/02/2020
Apple   15/02/2020
python list algorithm orders
2个回答
1
投票

我决定把它看成是按日期对各个水果进行排序，然后再把它们交错在一起.如果我把每个freuitdate设置成在时间上取决于下一个水果的日期，但只在相同的水果之间有时间上的依赖性btween；那么 拓扑排序 可用于将物品分成不同水果的子组，如上所述。然后，我可以按时间对第一个这样的组进行排序，然后随机对其他子组进行排序。

的代码。

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 29 09:21:15 2020

Answer to:
    https://stackoverflow.com/questions/61485884/sorting-items-but-preventing-same-named-items-being-next-to-eachother-also-addi

@author: Paddy3118
"""

from random import shuffle
from functools import reduce


def toposort2(data):
    "Based on: http://rosettacode.org/wiki/Topological_sort#Python"

    for k, v in data.items():
        v.discard(k) # Ignore self dependencies
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
    data.update({item:set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item,dep in data.items() if not dep)
        if not ordered:
            break
        #yield ' '.join(sorted(ordered))  ## The one change!!
        yield sorted(ordered)
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    assert not data, "A cyclic dependency exists amongst %r" % data

#%%

raw = """
Apple   10/02/2020
Apple   15/02/2020
Apple   10/03/2020
Apple   15/03/2020
Apple   10/04/2020
Apple   15/04/2020
Banana  16/03/2020
Banana  21/03/2020
Banana  16/04/2020
Orange  13/03/2020
Orange  15/03/2020
"""


def fruit_yearmonthday(fruitdate):
    "Order fields, (esp. dates), for item sorting"
    fruit, date = fruitdate
    d, m, y = date.split('/')
    return fruit, y, m, d


def ymd(fruitdate_string):
    "Order order field dates for partial order sorting"
    fruit, date = fruitdate_string.split()
    d, m, y = date.split('/')
    return y, m, d

#%%
# raw data into individual (frit, date) ruples
items = [tuple(line.split()) for line in raw.strip().split('\n')]
        # [('Apple', '10/02/2020'), ...]

# Order by date of each fruit kind
items.sort(key=fruit_yearmonthday)
    # [('Apple', '10/02/2020'),
    #  ('Apple', '15/02/2020'),
    #  ('Apple', '10/03/2020'),
    #  ('Apple', '15/03/2020'),
    #  ('Apple', '10/04/2020'),
    #  ('Apple', '15/04/2020'),
    #  ('Banana', '16/03/2020'),
    #  ('Banana', '21/03/2020'),
    #  ('Banana', '16/04/2020'),
    #  ('Orange', '13/03/2020'),
    #  ('Orange', '15/03/2020')]
# Stringify
items = [f"{i[0]:6}  {i[1]}" for i in items]

# Initial time-based dependencies only between _same_ fruits
last = items[0]
depends = {}
for fruitdate in items[1:]:
    if last[0] == fruitdate[0]:
        depends[last] = {fruitdate}
    last = fruitdate

partial_order = list(toposort2(depends))
#print("Partial ordering. items on same line could be in any order:\n")
#print ('\n'.join(str(line) for line in partial_order))
    # ['Apple   15/04/2020', 'Banana  16/04/2020', 'Orange  15/03/2020']
    # ['Apple   10/04/2020', 'Banana  21/03/2020', 'Orange  13/03/2020']
    # ['Apple   15/03/2020', 'Banana  16/03/2020']
    # ['Apple   10/03/2020']
    # ['Apple   15/02/2020']
    # ['Apple   10/02/2020']

# An ordering:
# First line by date, then other lines *randomly*
order = []
for linenum, line in enumerate(partial_order):
    if linenum == 0:
        order += sorted(line, key=ymd, reverse=True)
    else:
        shuffle(line)
        order += line

print("\nAN ORDERING OF ITEMS:")
for item in order:
    print(f'  {item}')

Sevral运行显示前三个项目和后三个项目总是相同的 但第四到第六个项目是随机的 第七到第八个项目也是如此

样本运行。

AN ORDERING OF ITEMS:
  Banana  16/04/2020
  Apple   15/04/2020
  Orange  15/03/2020
  Apple   10/04/2020
  Banana  21/03/2020
  Orange  13/03/2020
  Apple   15/03/2020
  Banana  16/03/2020
  Apple   10/03/2020
  Apple   15/02/2020
  Apple   10/02/2020

runcell(2, 'C:/Users/Paddy3118/Google Drive/Code/fruit_orderings.py')

AN ORDERING OF ITEMS:
  Banana  16/04/2020
  Apple   15/04/2020
  Orange  15/03/2020
  Orange  13/03/2020
  Banana  21/03/2020
  Apple   10/04/2020
  Apple   15/03/2020
  Banana  16/03/2020
  Apple   10/03/2020
  Apple   15/02/2020
  Apple   10/02/2020

runcell(2, 'C:/Users/Paddy3118/Google Drive/Code/fruit_orderings.py')

AN ORDERING OF ITEMS:
  Banana  16/04/2020
  Apple   15/04/2020
  Orange  15/03/2020
  Banana  21/03/2020
  Apple   10/04/2020
  Orange  13/03/2020
  Apple   15/03/2020
  Banana  16/03/2020
  Apple   10/03/2020
  Apple   15/02/2020
  Apple   10/02/2020

runcell(2, 'C:/Users/Paddy3118/Google Drive/Code/fruit_orderings.py')

AN ORDERING OF ITEMS:
  Banana  16/04/2020
  Apple   15/04/2020
  Orange  15/03/2020
  Apple   10/04/2020
  Orange  13/03/2020
  Banana  21/03/2020
  Banana  16/03/2020
  Apple   15/03/2020
  Apple   10/03/2020
  Apple   15/02/2020
  Apple   10/02/2020

runcell(2, 'C:/Users/Paddy3118/Google Drive/Code/fruit_orderings.py')

AN ORDERING OF ITEMS:
  Banana  16/04/2020
  Apple   15/04/2020
  Orange  15/03/2020
  Orange  13/03/2020
  Apple   10/04/2020
  Banana  21/03/2020
  Apple   15/03/2020
  Banana  16/03/2020
  Apple   10/03/2020
  Apple   15/02/2020
  Apple   10/02/2020
0
投票

我不确定我是否完全理解了整个问题 但我想我得到的是 "最近的项目，但没有相同的项目出现在旁边" 所以我要把重点放在这部分。

如果你能把相同的项目分开，同时保留它们之间的排序，那就很简单了；先按日期进行排序，然后再进行分离。 我想不出有哪个函数可以实现这种分离，所以我黑了一个 "足够好 "的函数，以产生合理的输出。

from datetime import datetime
from typing import Any, Callable, List, Optional, TypeVar

_I = TypeVar('_I')


def declump(
    items: List[_I], 
    key: Optional[Callable[[_I], Any]] = None
) -> None:
    """
    Separate identical items by doing repeated swaps of the form:
    AAB -> ABA  (in-place)
    Existing ordering is preserved within sets of identical items,
    but not between non-identical items.
    fixme: we can end up with a clump at the very end of the list!
    Easy workaround is to reverse the list and declump again.
    """
    if key is None:
        key = lambda x: x
    i = 0
    key(items[i])
    while i < len(items) - 2:
        if (
            key(items[i]) == key(items[i+1])
            and key(items[i+1]) != key(items[i+2])
        ):
            items[i+1], items[i+2] = items[i+2], items[i+1]
            if i > 0:
                i -= 1
                continue
        i += 1


produce = [
    ('Apple', '10/02/2020'),
    ('Apple', '15/02/2020'),
    ('Apple', '10/03/2020'),
    ('Apple', '15/03/2020'),
    ('Apple', '10/04/2020'),
    ('Apple', '15/04/2020'),
    ('Banana', '16/03/2020'),
    ('Banana', '21/03/2020'),
    ('Banana', '16/04/2020'),
    ('Orange', '13/03/2020'),
    ('Orange', '15/03/2020'),
]


produce.sort(key=lambda t: datetime.strptime(t[1], r'%d/%m/%Y'), reverse=True)
produce.reverse()
declump(produce, key=lambda t: t[0])
produce.reverse()
declump(produce, key=lambda t: t[0])
print('\n'.join(t[0].ljust(8) + t[1] for t in produce))

足够 "好"，产生合理的输出：

Apple   15/04/2020
Banana  16/04/2020
Apple   10/04/2020
Banana  21/03/2020
Apple   15/03/2020
Banana  16/03/2020
Apple   10/03/2020
Orange  15/03/2020
Apple   15/02/2020
Orange  13/03/2020
Apple   10/02/2020

我几乎可以肯定还有更好的方法来写这个函数 declump 函数，但把它翻过来再调用的笨拙似乎弥补了它的不足，所以我把改进留给读者去做。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.