给定一个列表,即: [1,1,2,2,3,5]
我想重新订购: [1,2,3,5,1,2]
评论后编辑:最终目标是最大化相同数字的任意两次出现之间的最小距离,或者最小化重复元素的紧密度并在列表中尽可能分散它们
重复问题: 分离相同类型项目的算法
我想出了这个解决方案,如果没有更好的建议,这就是我将使用的解决方案: https://stackoverflow.com/a/76792326/5053475
我可以使用什么算法?
按逻辑进行: 我正在考虑计算发生次数,比方说,即: [1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 44, 4, 5, 6, 1, 4, 5, 3, 6, 7, 8, 9, 11, 123 , 22, 44, 1, 5, 5]
将给出这个“出现次数”矩阵 2x30: [(3, 10), (1, 4), (5, 4), (44, 2), (4, 2), (6, 2), (7, 1), (8, 1), ( 9, 1), (11, 1), (123, 1), (22, 1)]
所以我会:
等等。 然后用不重复的数字填满空的位置。 当发生碰撞时(位置已被占据)交替+1、-1、+2、-2等直到找到空闲位置 我想出了这段代码,大胆地遵循我的算法,
from collections import defaultdict
def find_nearest_none(arr, position):
if arr[position] is None:
return position
step = 1
while True:
left_pos = position - step
right_pos = position + step
if left_pos >= 0 and arr[left_pos] is None:
return left_pos
elif right_pos < len(arr) and arr[right_pos] is None:
return right_pos
elif left_pos < 0 and right_pos >= len(arr):
# Both left and right positions are out of bounds
return False
step += 1
def max_distance_list(nums):
num_occurrences = {}
t = len(nums)
out = [None] * t
for num in nums:
num_occurrences[num] = num_occurrences.get(num, 0) + 1
num_occurrences = sorted(num_occurrences.items(), key=lambda item: item[1], reverse=True)
grouped_data = defaultdict(list)
for key, value in num_occurrences:
grouped_data[value].append(key)
print(grouped_data)
start_pos = 0
for x, y in dict(grouped_data).items():
print("Start pos:", start_pos)
for z in y:
sep = t // x
pos = start_pos;
for i in range(x):
free_pos = find_nearest_none(out, pos)
out[free_pos] = z
pos+=sep;
start_pos+=1;
return out
输出:[3, 1, 5, 3, 44, 4, 3, 6, 1, 3, 5, 7, 3, 8, 1, 3, 5, 44, 3, 4, 6, 3, 1, 5, 3, 9, 11, 3, 123, 22]
但这不是一个最佳结果,只是可以接受,而且离快速还很遥远。 是否有一些“已经完成”的功能可以更好更快地做到这一点?
如果没有,我将分批进行,并将使用这个“可接受”的结果,因为 它用于创建一个爬虫队列,以隔离对相同 IP 和/或域的调用
感谢任何帮助
您可以使用 Counter 类来确定每个数字的数量。然后按计数升序逐步构建列表。唯一的数字将排在前面。然后,对于出现两次的数字,最远的分布将是开头一个和结尾一个。除了两次重复之外,您仍然需要一个在开头,一个在结尾,但其余的应该通过将列表拆分为 count-1 块来均匀分布。
例如,Y 重复 4 次,应将一个放在开头,一个放在末尾,另外两个将项目分成 3 块。
...... --> Y..Y..Y..Y
该函数如下所示:
from collections import Counter
def spread(A):
result = []
for value,count in reversed(Counter(A).most_common()):
result.append(value)
if count == 1: continue
result.insert(0,value)
if count == 2: continue
chunk = (len(result)-2)//(count-1)
extra = len(result)-2-chunk*(count-1)
i = 0
for _ in range(count-2):
i += chunk + 1 + (extra>0)
extra -= 1
result.insert(i,value)
return result
输出:
A = [1,1,3,3,3,3,3,3,3,3,3,44,4,5,6,1,4,5,3,6,7,8,9,11,123,22,44,1,5,5]
spread(A)
[3,1,5,44,3,4,6,22,3,5,1,3,123,11,3,9,8,3,5,1,3,7,6,3,4,44,3,5,1,3]
出于比较目的,这里有一个函数,用于计算重复项之间的距离,返回每个距离处有多少个实例。
def repDist(A):
c = Counter(A[i:].index(n)+1 for i,n in enumerate(A,1) if n in A[i:])
return dict(sorted(c.items()))
OP = [3,1,5,3,44,4,3,6,1,3,5,7,3,8,1,3,5,44,3,4,6,3,1,5,3,9,11,3,123,22]
# {distance:count}
repDist(OP) # {3: 9, 6: 2, 7: 2, 8: 2, 13: 2, 14: 1}
repDist(spread(A)) # {3: 7, 4: 2, 7: 1, 9: 5, 16: 1, 19: 1, 22: 1}
比较匹配实例计数:
|----9---| |--------6--------| |------------3--------------|
OP: {3:9, 6:2, 7:2, 8:2, 13:2, 14:1}
spread: {3:7, 4:2, 7:1, 9:5, 16:1, 19:1, 22:1}
这是一个简单的算法。
我在这里所做的是查看列表中的每个元素。如果我这次没有看到它,我会将它添加到我的“收集”集中。如果我看到了它,我会把它放在一个新列表中,以便在下一次检查时进行检查。在遍历列表后,我对收集的元素进行排序并将它们添加到输出中。冲洗并重复,直到没有任何东西可以处理。
def reorder(undone):
out = []
while undone:
gather = set()
nextu = []
for n in undone:
if n in gather:
nextu.append(n)
else:
gather.add(n)
out.extend( sorted(gather) )
undone = nextu
return out
t1 = [1,1,2,2,3,5]
t2 = [1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 44, 4, 5, 6, 1, 4, 5, 3, 6, 7, 8, 9, 11, 123, 22, 44, 1, 5, 5]
print(reorder(t1))
print(reorder(t2))
输出:
[1, 2, 3, 5, 1, 2]
[1, 3, 4, 5, 6, 7, 8, 9, 11, 22, 44, 123, 1, 3, 4, 5, 6, 44, 1, 3, 5, 1, 3, 5, 3, 3, 3, 3, 3, 3]
我想不出比你实现的算法更好的算法,但我编写了一个更短(并且希望更快)的实现;嵌套循环当然可以改进,但我现在还不清楚如何改进;我也反向工作(能够在循环时从
free_indexes
中删除):
from collections import Counter
in_list = [1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 44, 4, 5, 6, 1, 4, 5, 3, 6, 7, 8, 9, 11, 123, 22, 44, 1, 5, 5]
out_list = [None] * len(in_list)
free_indexes = list(range(len(in_list)))
occurences = sorted(Counter(in_list).items(), key=lambda it:-it[1])
for value, count in occurences:
first = len(free_indexes) - 1
(step, last) = divmod(first, count - 1) if count > 1 else (1, first)
for i in range(first, last - 1, -step):
out_list[free_indexes[i]] = value
free_indexes.remove(free_indexes[i])
print(out_list)
# [5, 1, 3, 44, 4, 3, 6, 22, 3, 5, 1, 3, 123, 11, 3, 9, 8, 3, 5, 1, 3, 7, 6, 3, 4, 44, 3, 5, 1, 3]
您可以仅使用 pandas 函数
groupby
、reset_index
和 sort_values
来完成此操作。
import pandas as pd# Example numbers
df = pd.DataFrame({"num": [1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 44, 4, 5, 6, 1, 4, 5, 3, 6, 7, 8, 9, 11, 123, 22, 44, 1, 5, 5]})
result = (df
.groupby("num", as_index=False) # group
.apply(lambda g: g.reset_index(drop = True)) # index per group
.reset_index() # flat df
.sort_values(["level_1", "num"]) # sort on index
).num.values # get array
结果
array([ 1, 3, 4, 5, 6, 7, 8, 9, 11, 22, 44, 123, 1,
3, 4, 5, 6, 44, 1, 3, 5, 1, 3, 5, 3, 3,
3, 3, 3, 3], dtype=int64)